The Modified Negative Decision Number in Graphs

(1)

Volume 2011, Article ID 135481,9pages doi:10.1155/2011/135481

Research Article

The Modified Negative Decision Number in Graphs

Changping Wang

Department of Mathematics, Ryerson University, Toronto, ON, Canada M5B 2K3

Correspondence should be addressed to Changping Wang,[email protected] Received 14 December 2010; Accepted 11 January 2011

Academic Editor: Dalibor Froncek

Copyrightq2011 Changping Wang. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

A mappingx:V → {−1,1}is called negative if

u∈Nvxu≤1 for everyv∈V.The maximum of the values of

v∈Vxvtaken over all negative mappingsx, is called the modified negative decision number and is denoted byβ_DG. In this paper, several sharp upper bounds of this number for a general graph are presented. Exact values of these numbers for cycles, paths, cliques and bicliques are found.

1. Introduction

LetG V, Ebe a graph with vertex setV and edge set E. For a vertexv ∈ V, the open neighbourhood ofvinG isNv {u ∈ V | uv ∈ E}, and Nv Nv∪ {v}is its closed neighbourhood. For a graphG, and a subset S ⊆ V, we let deg_Sv denote the number of vertices inS joined tov. In particular, deg_Vv degv, the degree ofvinG. For disjoint subsets S and T of vertices, we use ES, T for the set of edges between S and T, and let eS, T |ES, T|. LetGSdenote the subgraph ofGinduced byS. For an integerk≥3, the bipartite graphK1,kis called a star, and the vertex of degreekis called the central vertex. Let x:V → ^Êbe a real-valued function. For convenience, we writexSfor

v∈SxvforS⊆V. In1, we initiated the study of the negative decision number in a graph. A functionx: VG → {−1,1}is called a bad function ofGifxNv≤1 for everyv∈VG. The maximum of the values ofxVG, taken over all bad functionsf, is called the negative decision number and is denoted byβDG.

The motivation for studying this parameter may be explained from a modelling perspective. For instance, by assigning the values −1 or 1 to the vertices of a graph, one can model networks of people in which global decisions must be made e.g., positive or negative responses. In certain circumstances, a positive decision can be made only if there are significantly more people voting for than those voting against. We assume that each

(2)

In the present paper, we study a variation of the negative decision number in a graph.

A mapping x : V → {−1,1} is called negative if

u∈Nvxu ≤ 1 for everyv ∈ V. The maximum of the values of

v∈Vxv, taken over all negative mappings x, is called the modified negative decision number and is denoted byβ_DG.

The parameterβ_Ddiﬀers significantly fromβD. For instance, for a cycleCnof ordern, β_DC_n∈{−2,−1,0}1see Theorem 5, whileβ_DC_n∈ { n/3, n/3−1}seeCorollary 2.6.

Throughout this paper, ifxis a negative mapping ofG, then we letPandQdenote the sets of those vertices ofGwhich are assignedunderxthe values1 and−1, respectively, and we letp|P|andq|Q|. Hence,xV p−q.

All graphs considered in this paper are simple, finite, and undirected. For a general reference on graph theory, the reader is referred to2,3. Notice thatβ_D G∪H β_DG β_DHfor two disjoint graphsGandH. Hence, we assume that all graphs are connected in this paper.

In the next section, we present several sharp upper bounds on the modified negative decision number for a general graph. We also establish sharp upper bounds on this number for bipartite graphs and regular graphs. Exact values of these numbers for cycles, paths, cliques, and bicliques are found.

2. Main Results

In this section, we investigate the modified negative decision number of a graph. We first present an upper bound on this number for a general graph in terms of its order.

For this purpose, we define a family Fof graphs as follows. LetF3 K1,2, and for k ≥ 4, letF_k be the graph obtained from the disjoint union of kstars K_1,k1 by adding all possible edges between the central vertices of thekstars. SeeFigure 1for an example ofF4. LetF{Fk|k≥3}.

Theorem 2.1. IfGis a graph of ordern≥2, then β_DG≤n2−2√

n1, 2.1

and this bound is sharp.

Proof. Letxbe a negative mapping such thatβ_DG xV. Thenβ_DG |P| − |Q|n−2q.

Note that every vertex inP must be joined to at least one vertex inQ. By the pigeonhole

(3)

Figure 1: A copy of the graphF4.

principle, at least one vertexvinQ is joined to at least|P|/|Q| n−q/qvertices in P.

Hence,

1≥xNv≥ −|Q|n−q

q −q−1 n

q. 2.2

That is,

q²2q−n≥0. 2.3

Solving the above inequality, we obtain that q≥ −1√

n1. 2.4

Thusβ_DG n−2q≤n2−2√ n1.

To see this bound is sharp, letG∈ F. Thus,GFkfor somek≥4. Hence,Ghas order n kk2, and sok √

n1−1. Assigning the value−1 to each of thekcentral vertices of the stars, and 1 to all other vertices, we define a negative mapping x of G satisfying xV k²n−2k n2−2√

n1. Thus,β_DG≥n2−2√

n1. It follows thatβ_DG n2−2√

n1.

Next we give an upper bound of the modified negative decision number for a general graph in terms of its order and size.

Theorem 2.2. IfGis a graph of ordern≥2 and sizem, then β_DG≤ 1

54m−n, 2.5

and this bound is sharp.

Proof. Letxbe a negative mapping such thatβ_DG xV. Thenβ_DG |P| − |Q|n−2q.

As every vertex inP must be joinedto at least one vertex inQ,eP, Q≥pn−q. For each

(4)

|EGQ| ≥ n−3q

2 . 2.8

Thus, the total number of edges inGis

m≥ |EGQ|eP, Q≥ n−3q

2 n−q. 2.9

So,q≥3n−2m/5. Hence,

β_D G n−2q≤ 1

54m−n. 2.10

To see this bound is sharp, letGFk∈ Ffor somek≥4 and letxbe the negative mapping of Gdefined in the proof ofTheorem 2.1. AsxV k²,β_D G≥k². On the other hand, asGhas ordernkk2and sizemkk1 kk−1/2,β_DG≤1/54m−n k². Therefore, β_DG 1/54m−n.

In the following theorem, we establish an upper bound of the modified negative decision number for a bipartite graph in terms of its order and we characterize the graphs attaining this bound. We define a familyHof bipartite graphs as follows.

Fork ≥ 1, letHk be the bipartite graph obtained from the disjoint union of 2k stars K_1,k2with centres{x1, x2, . . . , x_k, y1, y2, . . . , y_k}by adding all edges of the typex_iy_j, 1≤i, j ≤ k. SeeFigure 2for an example ofH2. LetH{Hk|k≥1}.

Theorem 2.3. IfGis a bipartite graph of ordern≥2, then β_D G≤n6−2√

2n9. 2.11

The equality holds if and only ifG∈ H.

Proof. Letxbe a negative mapping ofGsuch thatβ_DG xV. LetXandY be the partite sets ofG. Further, letX andX⁻ be the sets of vertices inX that are assigned the value1 and −1under x, respectively. Let Y and Y⁻ be defined analogously. ThenP X∪Y and Q X⁻ ∪Y⁻. For convenience, let|X| k,|X⁻| s,|Y| l and |Y⁻| t. Hence, β_DG kl−s−tn−2st.

(5)

Figure 2: A copy of the graphH2.

As every vertex inX must be joined to at least one vertex inY⁻, by the pigeonhole principle, at least one vertexvinY⁻is joined to at least|X|/|Y⁻|k/tvertices inX. Hence,

1≥xNv≥ −X⁻−1|X|

|Y⁻| −s−1 k

t. 2.12

Namely,

ts2≥k. 2.13

By a similar argument, one may show that

st2≥l. 2.14

Adding2.13and2.14, we have that

2st2st≥kl. 2.15

Thus,

nklst

≤2st3st

≤ 1

2st²3st.

2.16

Solving the above inequality forst, we obtain that st≥ −3√

2n9. 2.17

Thus,β_DG n−2st≤n6−2√ 2n9.

(6)

theorem first.

Theorem 2.4. For any integern≥2, one has

β_DKn

⎧⎪

⎨

⎪⎩

0 forneven;

1 fornodd. 2.18

For a generalk-regular graph, we have the following.

Theorem 2.5. IfGisk-regular graph of ordern, then

β_DG≤

⎧⎪

⎨

⎪⎩ n

k1

fork even;

0 fork odd.

2.19

This bound is sharp.

Proof. Letxbe any negative mapping ofG. AsGis ak-regular graph,

v∈V

xNv k1xV. 2.20

We discuss the following two cases.

Case 1. k is even. Sincexis a negative mapping, for every vertexv ∈ V,xNv ≤ 1. By 2.20, it follows that

k1xV≤n. 2.21

Hence,β_DG≤n/k1.

(7)

Case 2. kis odd. In this case,|Nv|is even for everyv∈V. So, for eachv∈V,xNv≤1 implies thatxNv≤0. Thus,

v∈V

xNv≤0. 2.22

By2.20, it follows thatk1xV≤0. Hence,β_DG≤0.

The sharpness follows fromTheorem 2.4.

Corollary 2.6. For any integern≥3, one has

β_D Cn

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ n

3

−1 n≡1mod 3;

n 3

otherwise.

2.23

Proof. AsCnis a 2-regular graph, byTheorem 2.5, we haveβ_DCn≤n/3. Letv1, v2, . . . , vnbe thenvertices ofC_nin a clockwise order. We discuss the following three cases.

Case 1. n3kfor some integerk. To show thatβ_D Cn k, it suﬃces to show that there is a negative mappingxofCnsuch thatxVCn k. In fact, assigning1,1,−1 starting with v1clockwise, and repeating, we produce a negative mappingxofC_nsatisfyingxVC_n k.

Case 2. n3k2 for some integerk. To show thatβ_D Cn k, it suﬃces to show that there is a negative mappingxofCnsuch thatxVCn k. In fact, if we assign 1,1,−1,1,−1 to the vertices in a clockwise order whenn 5, or assign 1,1,−1, . . ., 1,1,−1,1,−1 starting withv1

clockwise whenn >5, then we produce a negative mappingxofCnsatisfyingxVCn k.

Case 3. n 3k 1 for some integerk. To show that β_DCn ≥ k− 1, it suﬃces to show that there is a negative mapping xofC_n such thatxVC_n k−1. In fact, if we assign 1,−1,1,−1 to the vertices in a clockwise order when n 4, or assign 1,1,−1, . . . ,1,1,−1,−1 starting withv1clockwise whenn >4, then we produce a negative mappingxofCnsatisfying xVC_n k−1.

To showβ_DCn ≤k−1, we letxbe a negative mapping ofCn such thatxVCn

β_DCn. Soβ_DCn |P| − |Q|2p−n≤n/3. Hence,p≤2k, implying thatβ_DCn 2p−n≤ 2·2k−3k1 k−1.

Corollary 2.7. For any integern≥2, one has

β_DPn

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ n

3

−1 n≡1mod 3;

n 3

otherwise.

2.24

(8)

Thus,

v∈V

xNv≤n−2. 2.27

Note that

v∈VxNv 3xV−xv1−xv_n. So,

3xV−xv1−xvn≤n−2, 2.28

implying thatxV≤n−2xv1 xvn/3≤n/3.

For the bicliqueKn,n, we have the following result.

Theorem 2.8. For any integern≥2, one has

β_DKn,n

⎧⎨

⎩

0 forneven;

−2 fornodd. 2.29

Proof. LetX{u1, u2, . . . , un}andY {v1, v2, . . . , vn}be the partite sets ofKn,n. AsKn,nis an n-regular graph, byTheorem 2.5,β_DKn,n≤2n/n1<2. Hence,β_D Kn,n≤1. AsKn,nhas order 2n, which is even,

β_DKn,n≤0. 2.30

To prove the case when n is even, it suﬃces to show that there exists a negative mappingxof K_n,n such thatxVK_n,n 0. In fact, we can produce suchxby assigning xv_i xu_i −1ⁱ, 1≤i≤n.

Now we prove the case when nis odd. Let x be a negative mapping of Kn,n such thatβ_D K_n,n xVK_n,n. LetX,X⁻,Y, andY⁻ be defined the same as in the proof of Theorem 2.3. ThenP X∪YandQX⁻∪Y⁻. Let|X|k,|X⁻|s,|Y|land|Y⁻|t.

Thus,β_DKn,n kl−s−t2n−2st. Asβ_DKn,n≤0, by2.30, we have that

kl≤st. 2.31

(9)

Notice that we may assumek ≤ sand l ≤ t. Ifkl st, then k s and l t contradicting to the factksltn, wherenis odd. Hence,β_DK_n,n≤ −2.

To show thatβ_DKn,n −2, it suﬃces to show that there is a negative mappingxof Kn,n such that xVKn,n −2. In fact, we can produce such xby assigningxun −1, xu_i −1ⁱ⁻¹for 1≤i≤n−1 andxv_j −1^j, 1≤j≤n.

References

1 C. Wang, “The negative decision number in graphs,” The Australasian Journal of Combinatorics, vol. 41, pp. 263–272, 2008.

2 G. Chartrand and L. Lesniak, Graphs & Digraphs, Chapman & Hall, Boca Raton, Fla, USA, 3rd edition, 2000.

3 D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ, USA, 2nd edition, 2001.

(10)

Submit your manuscripts at http://www.hindawi.com

Hindawi Publishing Corporation

http://www.hindawi.com Volume 2014

Mathematics

^{Journal of}

Applied Mathematics^{Journal of}

Mathematical PhysicsAdvances in

Complex Analysis

^{Journal of}

Optimization

^{Journal of}

Combinatorics

International Journal of

Journal of

Function Spaces

Abstract and Applied Analysis

International Journal of Mathematics and Mathematical Sciences

Discrete Dynamics in Nature and Society

Discrete Mathematics

^{Journal of}

Stochastic Analysis

International Journal of