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
@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/}
}
TY  - JOUR
AU  - Hongyu Liang
TI  - Some Sharp Bounds on the Negative Decision Number of Graphs
JO  - Discussiones Mathematicae Graph Theory
PY  - 2013
SP  - 649
VL  - 33
IS  - 4
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267662/
LA  - en
ID  - DMGT_2013__33_4_267662
ER  - 
%0 Journal Article
%A Hongyu Liang
%T Some Sharp Bounds on the Negative Decision Number of Graphs
%J Discussiones Mathematicae Graph Theory
%D 2013
%P 649
%V 33
%N 4
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267662/
%G en
%F 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/