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 
@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},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2013},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a1/
%G en
%F DMGT_2013_33_4_a1
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/