- Tytuł:
- Bounds on the Signed 2-Independence Number in Graphs
- Autorzy:
- Volkmann, Lutz
- Powiązania:
- https://bibliotekanauki.pl/articles/29794119.pdf
- Data publikacji:
- 2013-09-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
bounds
signed 2-independence function
signed 2-independence number
Nordhaus-Gaddum type result - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 709-715
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł