Geodesic
Some Sharp Bounds on the Negative Decision Number of Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 649-656

Voir la notice de l'article provenant de la source Library of Science

Let G = (V,E) be a graph. A function f : V → -1,1 is called a bad function of G if ∑_u∈N_G(v) f(u) ≤ 1 for all v ∈ V where N_G(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.
Keywords: negative decision number, bad function, sharp upper bounds, Nordhaus-Gaddum results 
Liang, Hongyu. Some Sharp Bounds on the Negative Decision Number of Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 649-656. http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a1/
@article{DMGT_2013_33_4_a1,
     author = {Liang, Hongyu},
     title = {Some {Sharp} {Bounds} on the {Negative} {Decision} {Number} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {649--656},
     year = {2013},
     volume = {33},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a1/}
}
TY  - JOUR
AU  - Liang, Hongyu
TI  - Some Sharp Bounds on the Negative Decision Number of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 649
EP  - 656
VL  - 33
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a1/
LA  - en
ID  - DMGT_2013_33_4_a1
ER  - 
%0 Journal Article
%A Liang, Hongyu
%T Some Sharp Bounds on the Negative Decision Number of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 649-656
%V 33
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a1/
%G en
%F DMGT_2013_33_4_a1

[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