# Signed k-independence in graphs

Open Mathematics (2014)

- Volume: 12, Issue: 3, page 517-528
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topLutz Volkmann. "Signed k-independence in graphs." Open Mathematics 12.3 (2014): 517-528. <http://eudml.org/doc/269006>.

@article{LutzVolkmann2014,

abstract = {Let k ≥ 2 be an integer. A function f: V(G) → −1, 1 defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k − 1. That is, Σx∈N[v] f(x) ≤ k − 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σv∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α sk(G) of G. In this work, we mainly present upper bounds on α sk (G), as for example α sk(G) ≤ n − 2⌈(Δ(G) + 2 − k)/2⌉, and we prove the Nordhaus-Gaddum type inequality \[\alpha \_S^k \left( G \right) + \alpha \_S^k \left( \{\bar\{G\}\} \right) \leqslant n + 2k - 3\]
, where n is the order, Δ(G) the maximum degree and \[\bar\{G\}\]
the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.},

author = {Lutz Volkmann},

journal = {Open Mathematics},

keywords = {Bounds; Signed k-independence function; Signed k-independence number; Nordhaus-Gaddum type result; bounds; signed -independence function; signed -independence number},

language = {eng},

number = {3},

pages = {517-528},

title = {Signed k-independence in graphs},

url = {http://eudml.org/doc/269006},

volume = {12},

year = {2014},

}

TY - JOUR

AU - Lutz Volkmann

TI - Signed k-independence in graphs

JO - Open Mathematics

PY - 2014

VL - 12

IS - 3

SP - 517

EP - 528

AB - Let k ≥ 2 be an integer. A function f: V(G) → −1, 1 defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k − 1. That is, Σx∈N[v] f(x) ≤ k − 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σv∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α sk(G) of G. In this work, we mainly present upper bounds on α sk (G), as for example α sk(G) ≤ n − 2⌈(Δ(G) + 2 − k)/2⌉, and we prove the Nordhaus-Gaddum type inequality \[\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar{G}} \right) \leqslant n + 2k - 3\]
, where n is the order, Δ(G) the maximum degree and \[\bar{G}\]
the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.

LA - eng

KW - Bounds; Signed k-independence function; Signed k-independence number; Nordhaus-Gaddum type result; bounds; signed -independence function; signed -independence number

UR - http://eudml.org/doc/269006

ER -

## References

top- [1] Haynes T.W., Hedetniemi S.T., Slater P.J., Fundamentals of Domination in Graphs, Monogr. Textbooks Pure Appl. Math., 208, Marcel Dekker, New York, 1998 Zbl0890.05002
- [2] Haynes T.W., Hedetniemi S.T., Slater P.J. (Eds.), Domination in Graphs, Monogr. Textbooks Pure Appl. Math., 209, Marcel Dekker, New York, 1998 Zbl0890.05002
- [3] Henning M.A., Signed 2-independence in graphs, Discrete Math., 2002, 250(1–3), 93–107 http://dx.doi.org/10.1016/S0012-365X(01)00275-8 Zbl1003.05076
- [4] Shan E., Sohn M.Y., Kang L., Upper bounds on signed 2-independence numbers of graphs, Ars Combin., 2003, 69, 229–239 Zbl1073.05559
- [5] Turán P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 1941, 48, 436–452 (in Hungarian)
- [6] Volkmann L., Bounds on the signed 2-independence number in graphs, Discuss. Math. Graph Theory, 2013, 33(4), 709–715 http://dx.doi.org/10.7151/dmgt.1686 Zbl1295.05182
- [7] Zelinka B., On signed 2-independence numbers of graphs (manuscript)

## NotesEmbed ?

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