Bounds on the Signed 2-Independence Number in Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 709-715
Voir la notice de l'article provenant de la source Library of Science
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 α_s^2(G) of G. In this work, we mainly present upper bounds on α_s^2(G), as for example α_s^2(G) ≤ n−2 [∆ (G)//2], and we prove the Nordhaus-Gaddum type inequality α_s^2 (G) + α_s^2(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
@article{DMGT_2013_33_4_a6,
author = {Volkmann, Lutz},
title = {Bounds on the {Signed} {2-Independence} {Number} in {Graphs}},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {709--715},
publisher = {mathdoc},
volume = {33},
number = {4},
year = {2013},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a6/}
}
Volkmann, Lutz. Bounds on the Signed 2-Independence Number in Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 709-715. http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a6/