# Bounds on the Signed 2-Independence Number in Graphs

• Volume: 33, Issue: 4, page 709-715
• ISSN: 2083-5892

top

## Abstract

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

## How to cite

top

Lutz Volkmann. "Bounds on the Signed 2-Independence Number in Graphs." Discussiones Mathematicae Graph Theory 33.4 (2013): 709-715. <http://eudml.org/doc/268105>.

@article{LutzVolkmann2013,
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 α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.},
author = {Lutz Volkmann},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {bounds; signed 2-independence function; signed 2-independence number; Nordhaus-Gaddum type result; Nordhaus-Gaddum-type result},
language = {eng},
number = {4},
pages = {709-715},
title = {Bounds on the Signed 2-Independence Number in Graphs},
url = {http://eudml.org/doc/268105},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Lutz Volkmann
TI - Bounds on the Signed 2-Independence Number in Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 4
SP - 709
EP - 715
AB - 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.
LA - eng
KW - bounds; signed 2-independence function; signed 2-independence number; Nordhaus-Gaddum type result; Nordhaus-Gaddum-type result
UR - http://eudml.org/doc/268105
ER -

## References

top
1. [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. Zbl0842.05051
2. [2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
3. [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcel Dekker, Inc., New York, 1998). Zbl0883.00011
4. [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. [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. Zbl1073.05559
6. [6] P. Turán, On an extremal problem in graph theory, Math. Fiz. Lapok 48 (1941) 436-452.
7. [7] B. Zelinka, On signed 2-independence numbers of graphs, manuscript. Zbl1081.05042

top

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.