Discussiones Mathematicae Graph Theory 33(4) (2013)
709-715
DOI: https://doi.org/10.7151/dmgt.1686
Bounds on the signed 2-independence number in graphs
| Lutz Volkmann
Lehrstuhl II für Mathematik |
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. |
Received 21 February 2012
Revised 3 September 2012
Accepted 3 September 2012
Close