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 α2s(G) of G. In this work, we mainly present upper bounds on α2s(G), as for example α2s(G) ≤ n−2 [∆ (G)/2], and we prove the Nordhaus-Gaddum type inequality α2s (G) + α2s(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.
@article{bwmeta1.element.doi-10_7151_dmgt_1686,
author = {Lutz Volkmann},
title = {Bounds on the Signed 2-Independence Number in Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {709-715},
zbl = {1295.05182},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1686}
}
Lutz Volkmann. Bounds on the Signed 2-Independence Number in Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 709-715. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1686/
[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. | Zbl 0842.05051
[2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). | Zbl 0890.05002
[3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcel Dekker, Inc., New York, 1998). | Zbl 0883.00011
[4] M.A. Henning, Signed 2-independence in graphs, Discrete Math. 250 (2002) 93-107. doi:10.1016/S0012-365X(01)00275-8[Crossref]
[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. | Zbl 1073.05559
[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. | Zbl 1081.05042