# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## Bounds on the signed 2-independence number in graphs

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

## Abstract

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.

## References

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