Bounds on the Signed 2-Independence Number in Graphs

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 -