Some Sharp Bounds on the Negative Decision Number of Graphs

Hongyu Liang

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 4, page 649-656
  • ISSN: 2083-5892

Abstract

top
Let G = (V,E) be a graph. A function f : V → {-1,1} is called a bad function 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∈V f(v) taken over all bad functions 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.

How to cite

top

Hongyu Liang. "Some Sharp Bounds on the Negative Decision Number of Graphs." Discussiones Mathematicae Graph Theory 33.4 (2013): 649-656. <http://eudml.org/doc/267662>.

@article{HongyuLiang2013,
abstract = {Let G = (V,E) be a graph. A function f : V → \{-1,1\} is called a bad function 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∈V f(v) taken over all bad functions 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.},
author = {Hongyu Liang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {negative decision number; bad function; sharp upper bounds; Nordhaus-Gaddum results},
language = {eng},
number = {4},
pages = {649-656},
title = {Some Sharp Bounds on the Negative Decision Number of Graphs},
url = {http://eudml.org/doc/267662},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Hongyu Liang
TI - Some Sharp Bounds on the Negative Decision Number of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 4
SP - 649
EP - 656
AB - Let G = (V,E) be a graph. A function f : V → {-1,1} is called a bad function 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∈V f(v) taken over all bad functions 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.
LA - eng
KW - negative decision number; bad function; sharp upper bounds; Nordhaus-Gaddum results
UR - http://eudml.org/doc/267662
ER -

References

top
  1. [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[WoS][Crossref] 
  2. [2] R. Diestel, Graph Theory (Fourth Edition, Springer-Verlag, 2010). 
  3. [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. Zbl0842.05051
  4. [4] O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287-293. doi:10.1016/0012-365X(96)00026-X[Crossref] 
  5. [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[Crossref] Zbl0933.05117
  6. [6] F. Harary, Graph Theory (Addison-Wesley, 1969). 
  7. [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, 1998). Zbl0883.00011
  8. [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1998). Zbl0890.05002
  9. [9] M.A. Henning, Signed total domination in graphs, Discrete Math. 278 (2004) 109-125. doi:10.1016/j.disc.2003.06.002[Crossref] 
  10. [10] J. Matouˇsek, On the signed domination in graphs, Combinatorica 20 (2000) 103-108. doi:10.1007/s004930070034[Crossref] 
  11. [11] L. Volkmann, Signed domination and signed domatic numbers of digraphs, Discuss. Math. Graph Theory 31 (2011) 415-427. doi:10.7151/dmgt.1555[Crossref] Zbl1227.05207
  12. [12] C. Wang, The negative decision number in graphs, Australas. J. Combin. 41 (2008) 263-272. Zbl1154.05050
  13. [13] C. Wang, The signed matchings in graphs, Discuss. Math. Graph Theory 28 (2008) 477-486. doi:10.7151/dmgt.1421[Crossref] 
  14. [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[Crossref] Zbl1221.05276
  15. [15] C. Wang, Voting ‘against’ in regular and nearly regular graphs, Appl. Anal. Discrete Math. 4 (2010) 207-218. doi:10.2298/AADM100213014W[Crossref][WoS] Zbl1265.05519
  16. [16] B. Zelinka, Signed total domination number of a graph, Czechoslovak Math. J. 51 (2001) 225-229. doi:10.1023/A:1013782511179[Crossref] Zbl0977.05096
  17. [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 Zbl0928.05052

NotesEmbed ?

top

You must be logged in to post comments.