PDF
Discussiones Mathematicae Graph Theory 33(4) (2013)
649-656
DOI: https://doi.org/10.7151/dmgt.1683
Some Sharp Bounds on the Negative Decision Number of Graphs
| Hongyu Liang
Institute for Interdisciplinary Information Sciences |
Abstract
Let G = (V,E) be a graph. A function f:V → { −1,1} is called a of G if ∑u ∈ NG(v)f(u) ≤ 1 for all v ∈ V, where NG(v) denotes the set of neighbors of v in G. The negative decision number of G, introduced in [12], is the maximum value of ∑v ∈ Vf(v) taken over all s of G. In this paper, we present sharp upper bounds on the negative decision number of a graph in terms of its order, minimum degree, and maximum degree. We also establish a sharp Nordhaus-Gaddum-type inequality for the negative decision number.
Keywords: negative decision number, bad function, sharp upper bounds, Nordhaus-Gaddum results
2010 Mathematics Subject Classification: 05C69, 05C75.
References
| [1] | W. Chen and E. Song, Lower bounds on several versions of signed domination number, Discrete Math. 308 (2008) 1837--1846, doi: 10.1016/j.disc.2006.09.050. |
| [2] | R. Diestel, Graph Theory (Fourth Edition, Springer-Verlag, 2010). |
| [3] | J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs, Graph Theory, Combinatorics, and Applications 1 (1995) 311--322. |
| [4] | O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287--293, doi: 10.1016/0012-365X(96)00026-X. |
| [5] | Z. Füredi and D. Mubayi, Signed domination in regular graphs and set-systems, J. Combin. Theory (B) 76 (1999) 223--239, doi: 10.1006/jctb.1999.1905. |
| [6] | F. Harary, Graph Theory ( Addison-Wesley, 1969). |
| [7] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, 1998). |
| [8] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs ( Marcel Dekker, 1998). |
| [9] | M.A. Henning, Signed total domination in graphs, Discrete Math. 278 (2004) 109--125, doi: 10.1016/j.disc.2003.06.002. |
| [10] | J. Matoušek, On the signed domination in graphs, Combinatorica 20 (2000) 103--108, doi: 10.1007/s004930070034. |
| [11] | L. Volkmann, Signed domination and signed domatic numbers of digraphs, Discuss. Math. Graph Theory 31 (2011) 415--427, doi: 10.7151/dmgt.1555. |
| [12] | C. Wang, The negative decision number in graphs, Australas. J. Combin. 41 (2008) 263--272. |
| [13] | C. Wang, The signed matchings in graphs, Discuss. Math. Graph Theory 28 (2008) 477--486, doi: 10.7151/dmgt.1421. |
| [14] | C. Wang, Lower negative decision number in a graph, J. Appl. Math. Comput. 34 (2010) 373--384, doi: 10.1007/s12190-009-0327-5. |
| [15] | C. Wang, Voting `against' in regular and nearly regular graphs, Appl. Anal. Discrete Math. 4 (2010) 207--218, doi: 10.2298/AADM100213014W. |
| [16] | B. Zelinka, Signed total domination number of a graph, Czechoslovak Math. J. 51 (2001) 225--229, doi: 10.1023/A:1013782511179. |
| [17] | Z. Zhang, B. Xu, Y. Li and L. Liu, A note on the lower bounds of signed domination number of a graph, Discrete Math. 195 (1999) 295--298, doi: 0.1016/S0012-365X(98)00189-7. |
Received 27 July 2011
Revised 20 July 2012
Accepted 23 July 2012
Close