Geodesic
Bounds on the Signed 2-Independence Number in Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 709-715.

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

Let G be a finite and simple graph with vertex set V (G), and let f V (G) → −1, 1 be a two-valued function. If ∑_x∈N|v| f(x) ≤ 1 for each v ∈ V (G), where N[v] is the closed neighborhood of v, then f is a signed 2-independence function on G. The weight of a signed 2-independence function f is w(f) = ∑_v∈V (G) f(v). The maximum of weights w(f), taken over all signed 2-independence functions f on G, is the signed 2-independence number α_s^2(G) of G. In this work, we mainly present upper bounds on α_s^2(G), as for example α_s^2(G) ≤ n−2 [∆ (G)//2], and we prove the Nordhaus-Gaddum type inequality α_s^2 (G) + α_s^2(G) ≤ n+1, where n is the order and ∆ (G) is the maximum degree of the graph G. Some of our theorems improve well-known results on the signed 2-independence number.
Keywords: bounds, signed 2-independence function, signed 2-independence number, Nordhaus-Gaddum type result 
@article{DMGT_2013_33_4_a6,
     author = {Volkmann, Lutz},
     title = {Bounds on the {Signed} {2-Independence} {Number} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {709--715},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a6/}
}
TY  - JOUR
AU  - Volkmann, Lutz
TI  - Bounds on the Signed 2-Independence Number in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 709
EP  - 715
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a6/
LA  - en
ID  - DMGT_2013_33_4_a6
ER  - 
%0 Journal Article
%A Volkmann, Lutz
%T Bounds on the Signed 2-Independence Number in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 709-715
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a6/
%G en
%F DMGT_2013_33_4_a6
Volkmann, Lutz. Bounds on the Signed 2-Independence Number in Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 709-715. http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a6/

[1] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs, in: Graph Theory, Combinatorics, and Applications (John Wiley and Sons, Inc. 1, 1995) 311-322.

[2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).

[3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcel Dekker, Inc., New York, 1998).

[4] M.A. Henning, Signed 2-independence in graphs, Discrete Math. 250 (2002) 93-107. doi:10.1016/S0012-365X(01)00275-8

[5] E.F. Shan, M.Y. Sohn and L.Y. Kang, Upper bounds on signed 2-independence numbers of graphs, Ars Combin. 69 (2003) 229-239.

[6] P. Turán, On an extremal problem in graph theory, Math. Fiz. Lapok 48 (1941) 436-452.

[7] B. Zelinka, On signed 2-independence numbers of graphs, manuscript.