# The Modified Negative Decision Number in Graphs

Authors: Changping Wang
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## Abstract

A mappingx:V→{-1,1} is called negative if ∑u∈N[v]x(u)≤1 for every v∈V. The maximum of the values of ∑v∈Vx(v) taken over all negative mappings x, is called the modified negative decision number and is denoted by βD′(G). 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.


---

## Body

## 1. Introduction

LetG=(V,E) be a graph with vertex set V and edge set E. For a vertex v∈V, the open neighbourhood of v in G is N(v)={u∈V∣uv∈E}, and N[v]=N(v)∪{v} is its closed neighbourhood. For a graph G, and a subset S⊆V, we let degS(v) denote the number of vertices in S joined to v. In particular, degV(v)=deg(v), the degree of v in G. For disjoint subsets S and T of vertices, we use E(S,T) for the set of edges between S and T, and let e(S,T)=|E(S,T)|. Let G[S] denote the subgraph of G induced by S. For an integer k≥3, the bipartite graph K1,k is called a star, and the vertex of degree k is called the central vertex. Let x:V→ℝ be a real-valued function. For convenience, we write x(S) for ∑v∈Sx(v) for S⊆V.In [1], we initiated the study of the negative decision number in a graph. A function x:V(G)→{-1,1} is called a bad function of G if x(N(v))≤1 for every v∈V(G). The maximum of the values of x(V(G)), taken over all bad functions f, is called the negative decision number and is denoted by βD(G).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 individual has one vote, and each has an initial opinion. We assign 1 to vertices (individuals) which have a positive opinion and −1 to vertices which have a negative opinion. A voter votes “good” if there are at least two more vertices in its open neighbourhood with positive opinion than with negative opinion, otherwise the vote is “bad”. We seek an assignment of opinions that guarantee a unanimous decision; namely, for which every vertex votes “bad”. Such an assignment of opinions is called a uniformly negative assignment. Among all uniformly negative assignments of opinions, we are particularly interested in the minimum number of vertices (individuals) which have a negative opinion. The negative decision number is the maximum possible sum of all opinions, 1 for a positive opinion and −1 for a negative opinion, in a uniformly negative assignment of opinions. The negative decision number corresponds to the minimum number of individuals who can have negative opinions and in doing so force every individual to vote bad.In the present paper, we study a variation of the negative decision number in a graph. A mappingx:V→{-1,1} is called negative if ∑u∈N[v]x(u)≤1 for every v∈V. The maximum of the values of ∑v∈Vx(v), taken over all negative mappings x, is called the modified negative decision number and is denoted by βD′(G).The parameterβD′ differs significantly from βD. For instance, for a cycle Cn of order n, βD(Cn)∈{-2,-1,0} ([1] see Theorem 5), while βD′(Cn)∈{⌊n/3⌋,⌊n/3-1⌋} (see Corollary 2.6).Throughout this paper, ifx is a negative mapping of G, then we let P and Q denote the sets of those vertices of G which are assigned (under x) the values +1 and −1, respectively, and we let p=|P| and q=|Q|. Hence, x(V)=p-q.All graphs considered in this paper are simple, finite, and undirected. For a general reference on graph theory, the reader is referred to [2, 3]. Notice that βD′(G∪H)=βD′(G)+βD′(H) for two disjoint graphs G and H. 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ℱ of graphs as follows. Let F3=K1,2, and for k≥4, let Fk be the graph obtained from the disjoint union of k stars K1,k+1 by adding all possible edges between the central vertices of the k stars. See Figure 1 for an example of F4. Let ℱ={Fk∣k≥3}.Figure 1
A copy of the graphF4.Theorem 2.1.
IfG is a graph of order n≥2, then
(2.1)βD′(G)≤n+2-2n+1,
and this bound is sharp.Proof.
Letx be a negative mapping such that βD′(G)=x(V). Then βD′(G)=|P|-|Q|=n-2q. Note that every vertex in P must be joined to at least one vertex in Q. By the pigeonhole principle, at least one vertex v in Q is joined to at least |P|/|Q|=(n-q)/q vertices in P. Hence,
(2.2)1≥x(N[v])≥-|Q|+n-qq=-q-1+nq.
That is,
(2.3)q2+2q-n≥0.
Solving the above inequality, we obtain that
(2.4)q≥-1+n+1.
Thus βD′(G)=n-2q≤n+2-2n+1.
To see this bound is sharp, letG∈ℱ. Thus, G=Fk for some k≥4. Hence, G has order n=k(k+2), and so k=n+1-1. Assigning the value −1 to each of the k central vertices of the stars, and +1 to all other vertices, we define a negative mapping x of G satisfying x(V)=k2=n-2k=n+2-2n+1. Thus, βD′(G)≥n+2-2n+1. It follows that βD′(G)=n+2-2n+1.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.
IfG is a graph of order n≥2 and size m, then
(2.5)βD′(G)≤15(4m-n),
and this bound is sharp.Proof.
Letx be a negative mapping such that βD′(G)=x(V). Then βD′(G)=|P|-|Q|=n-2q. As every vertex in P must be joined to at least one vertex in Q,  e(P,Q)≥p=n-q. For each vertex v of Q, degQ(v)≥degP(v)-2, and hence,
(2.6)n-q≤e(P,Q)=∑v∈Qdeg⁡P(v)≤∑v∈Q(deg⁡Q(v)+2).
Namely,
(2.7)n-q≤2|E(G[Q])|+2q.
Hence,
(2.8)|E(G[Q])|≥n-3q2.
Thus, the total number of edges in G is
(2.9)m≥|E(G[Q])|+e(P,Q)≥n-3q2+n-q.
So, q≥(3n-2m)/5. Hence,
(2.10)βD′(G)=n-2q≤15(4m-n).
To see this bound is sharp, let G=Fk∈ℱ for some k≥4 and let x be the negative mapping of G defined in the proof of Theorem 2.1. As x(V)=k2, βD′(G)≥k2. On the other hand, as G has order n=k(k+2) and size m=k(k+1)+k(k-1)/2, βD′(G)≤(1/5)(4m-n)=k2. Therefore, βD′(G)=(1/5)(4m-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 familyℋ of bipartite graphs as follows.Fork≥1, let Hk be the bipartite graph obtained from the disjoint union of 2k stars K1,k+2 with centres {x1,x2,…,xk,y1,y2,…,yk} by adding all edges of the type xiyj, 1≤i,j≤k. See Figure 2 for an example of H2. Let ℋ={Hk∣k≥1}.Figure 2
A copy of the graphH2.Theorem 2.3.
IfG is a bipartite graph of order n≥2, then
(2.11)βD′(G)≤n+6-22n+9.
The equality holds if and only if G∈ℋ.Proof.
Letx be a negative mapping of G such that βD′(G)=x(V). Let X and Y be the partite sets of G. Further, let X+ and X- be the sets of vertices in X that are assigned the value +1 and −1 (under x), respectively. Let Y+ and Y- be defined analogously. Then P=X+∪Y+ and Q=X-∪Y-. For convenience, let |X+|=k, |X-|=s, |Y+|=l and |Y-|=t. Hence, βD′(G)=k+l-s-t=n-2(s+t).
As every vertex inX+ must be joined to at least one vertex in Y-, by the pigeonhole principle, at least one vertex v in Y- is joined to at least |X+|/|Y-|=k/t vertices in X+. Hence,
(2.12)1≥x(N[v])≥-|X-|-1+|X+||Y-|=-s-1+kt.
Namely,
(2.13)t(s+2)≥k.
By a similar argument, one may show that
(2.14)s(t+2)≥l.
Adding (2.13) and (2.14), we have that
(2.15)2st+2(s+t)≥k+l.
Thus,
(2.16)n=k+l+s+t≤2st+3(s+t)≤12(s+t)2+3(s+t).
Solving the above inequality for s+t, we obtain that
(2.17)s+t≥-3+2n+9.
Thus, βD′(G)=n-2(s+t)≤n+6-22n+9.
IfβD′(G)=n+6-22n+9, then by the above analysis, we have s=t and k=l=s(s+2). Moreover, each vertex of X+ (resp., Y+) has degree 1 and is joined to one vertex of Y- (resp., X-), while each vertex of Y- is joined to all vertices of X- and s+2 vertices of X+ and each vertex of X- is joined to all vertices of Y- and s+2 vertices of Y+. Thus, βD′(G)=n+6-22n+9 implies that G∈ℋ.
IfG∈ℋ, then G=Hk for some k≥1. Hence, G has order n=2k(k+3), and so k=(1/2)(2n+9-3). Assigning to the k central vertices of the stars the value −1, and to all other vertices +1, we define a negative mapping x of G satisfying x(V)=2k(k+1)=n+6-22n+9. Hence, βD′(G)≥n+6-22n+9. It follows that βD′(G)=n+6-22n+9.Finally, we present an upper bound of the modified negative decision number for a regular graph in terms of its order in Theorem2.5. We encourage the reader to verify our next theorem first.Theorem 2.4.
For any integern≥2, one has
(2.18)βD′(Kn)={0forneven;1fornodd.For a generalk-regular graph, we have the following.Theorem 2.5.
IfG is k-regular graph of order n, then
(2.19)βD′(G)≤{⌊nk+1⌋forkeven;0forkodd.
This bound is sharp.Proof.
Letx be any negative mapping of G. As G is a k-regular graph,
(2.20)∑v∈Vx(N[v])=(k+1)x(V).
We discuss the following two cases.Case 1.
k is even. Since x is a negative mapping, for every vertex v∈V, x(N[v])≤1. By (2.20), it follows that
(2.21)(k+1)x(V)≤n.
Hence, βD′(G)≤n/(k+1).Case 2.
k is odd. In this case, |N[v]| is even for every v∈V. So, for each v∈V, x(N[v])≤1 implies that x(N[v])≤0. Thus,
(2.22)∑v∈Vx(N[v])≤0.
By (2.20), it follows that (k+1)x(V)≤0. Hence, βD′(G)≤0.The sharpness follows from Theorem 2.4.Corollary 2.6.
For any integern≥3, one has
(2.23)βD′(Cn)={⌊n3⌋-1n≡1(mod⁡3);⌊n3⌋otherwise.Proof.
AsCn is a 2-regular graph, by Theorem 2.5, we have βD′(Cn)≤n/3. Let v1,v2,…,vn be the n vertices of Cn in a clockwise order. We discuss the following three cases.
Case 1.
n=3k for some integer k. To show that βD′(Cn)=k, it suffices to show that there is a negative mapping x of Cn such that x(V(Cn))=k. In fact, assigning +1,+1,-1 starting with v1 clockwise, and repeating, we produce a negative mapping x of Cn satisfying x(V(Cn))=k.Case 2.
n=3k+2 for some integer k. To show that βD′(Cn)=k, it suffices to show that there is a negative mapping x of Cn such that x(V(Cn))=k. In fact, if we assign 1,1,-1,1,-1 to the vertices in a clockwise order when n=5, or assign 1,1,-1,…, 1,1,-1,1,-1 starting with v1 clockwise when n>5, then we produce a negative mapping x of Cn satisfying x(V(Cn))=k.Case 3.
n=3k+1 for some integer k. To show that βD′(Cn)≥k-1, it suffices to show that there is a negative mapping x of Cn such that x(V(Cn))=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 with v1 clockwise when n>4, then we produce a negative mapping x of Cn satisfying x(V(Cn))=k-1.
To showβD′(Cn)≤k-1, we let x be a negative mapping of Cn such that x(V(Cn))=βD′(Cn). So βD′(Cn)=|P|-|Q|=2p-n≤n/3. Hence, p≤2k, implying that βD′(Cn)=2p-n≤2·2k-(3k+1)=k-1.Corollary 2.7.
For any integern≥2, one has
(2.24)βD′(Pn)={⌊n3⌋-1n≡1(mod⁡3);⌊n3⌋otherwise.Proof.
It is easy to see that Corollary2.7 is true for 2≤n≤4. So we may assume that n≥5. Let v1,v2,…,vn be the n vertices of Pn with end vertices v1 and vn. We only show that βD′(Pn)≤n/3. The rest of the proof is similar to that of Corollary 2.6, so is omitted.
Take any negative mappingx of Pn. For i=1 or n, as deg(vi)=1, we have that(2.25)x(N[vi])≤0.
For 1<i<n,deg(vi)=2. Hence,
(2.26)x(N[vi])≤1.
Thus,
(2.27)∑v∈Vx(N[v])≤n-2.
Note that∑v∈Vx(N[v])=3x(V)-x(v1)-x(vn). So,(2.28)3x(V)-x(v1)-x(vn)≤n-2,
implying that x(V)≤(n-2+x(v1)+x(vn))/3≤n/3.For the bicliqueKn,n, we have the following result.Theorem 2.8.
For any integern≥2, one has
(2.29)βD′(Kn,n)={0forneven;-2fornodd.Proof.
LetX={u1,u2,…,un} and Y={v1,v2,…,vn} be the partite sets of Kn,n. As Kn,n is an n-regular graph, by Theorem 2.5, βD′(Kn,n)≤2n/(n+1)<2. Hence, βD′(Kn,n)≤1. As Kn,n has order 2n, which is even,
(2.30)βD′(Kn,n)≤0.
To prove the case whenn is even, it suffices to show that there exists a negative mapping x of Kn,n such that x(V(Kn,n))=0. In fact, we can produce such x by assigning x(vi)=x(ui)=(-1)i, 1≤i≤n.
Now we prove the case whenn is odd. Let x be a negative mapping of Kn,n such that βD′(Kn,n)=x(V(Kn,n)). Let X+, X-, Y+, and Y- be defined the same as in the proof of Theorem 2.3. Then P=X+∪Y+ and Q=X-∪Y-. Let |X+|=k, |X-|=s, |Y+|=l and |Y-|=t. Thus, βD′(Kn,n)=k+l-s-t=2n-2(s+t). As βD′(Kn,n)≤0, by (2.30), we have that
(2.31)k+l≤s+t.
Notice that we may assumek≤s and l≤t. If k+l=s+t, then k=s and l=t contradicting to the fact k+s=l+t=n, where n is odd. Hence, βD′(Kn,n)≤-2.
To show thatβD′(Kn,n)=-2, it suffices to show that there is a negative mapping x of Kn,n such that x(V(Kn,n))=-2. In fact, we can produce such x by assigning x(un)=-1, x(ui)=(-1)i-1 for 1≤i≤n-1 and x(vj)=(-1)j, 1≤j≤n.



---

*Source: 135481-2011-02-24.xml*