# Bounds on the Signed 2-Independence Number in Graphs

Discussiones Mathematicae Graph Theory (2013)

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

## Access Full Article

top## Abstract

top## How to cite

topLutz 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] 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] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
- [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] 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. Zbl1073.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. Zbl1081.05042

## Citations in EuDML Documents

top## NotesEmbed ?

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