Some Sharp Bounds on the Negative Decision Number of Graphs
Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 4, p. 649.
Voir la notice de l'article dans European Digital Mathematics Library
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.
Classification :
05C35, 05C69, 05C75
Mots-clés : negative decision number, bad function, sharp upper bounds, Nordhaus-Gaddum results
Mots-clés : negative decision number, bad function, sharp upper bounds, Nordhaus-Gaddum results
@article{DMGT_2013__33_4_267662, author = {Hongyu Liang}, title = {Some {Sharp} {Bounds} on the {Negative} {Decision} {Number} of {Graphs}}, journal = {Discussiones Mathematicae Graph Theory}, pages = {649}, publisher = {mathdoc}, volume = {33}, number = {4}, year = {2013}, zbl = {1295.05177}, language = {en}, url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267662/} }
Hongyu Liang. Some Sharp Bounds on the Negative Decision Number of Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 4, p. 649. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267662/