Discussiones Mathematicae Graph Theory 33(4) (2013) 709-715
doi: 10.7151/dmgt.1686

[BIBTex] [PDF] [PS]

Bounds on the signed 2-independence number in graphs

Lutz Volkmann

Lehrstuhl II für Mathematik
RWTH-Aachen University
52056 Aachen, Germany


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 αs2(G) of G.

In this work, we mainly present upper bounds on αs2(G), as for example αs2(G) ≤ n −2 ⌈ Δ(G)/2 ⌉, and we prove the Nordhaus-Gaddum type inequality αs2(G)+ αs2(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

2010 Mathematics Subject Classification: 05C69.


[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.

Received 21 February 2012
Revised 3 September 2012
Accepted 3 September 2012