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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.