Independence in connected graphs

Harant, Jochen GND; Rautenbach, Dieter GND

We prove that if $G=(V_G,E_G)$ is a finite, simple, and undirected graph with $\kappa$ components and independence number $\alpha(G)$, then there exist a positive integer $k\in \mathbb{N}$ and a function $f:V_G\to \mathbb{N}_0$ with non-negative integer values such that $f(u)\leq d_G(u)$ for $u\in V_G$, $\alpha(G)\geq k\geq \sum\limits_{u\in V_G}\frac{1}{d_G(u)+1-f(u)},$ and $\sum\limits_{u\in V_G}f(u)\geq 2(k-\kappa).$ This result is a best-possible improvement of a result due to Harant and Schiermeyer (On the independence number of a graph in terms of order and size, {\it Discrete Math.} {\bf 232} (2001), 131-138) and implies that $\frac{\alpha(G)}{n(G)}\geq \frac{2}{\left(d(G)+1+\frac{2}{n(G)}\right)+\sqrt{\left(d(G)+1+\frac{2}{n(G)}\right)2-8}}$ for connected graphs $G$ of order $n(G)$, average degree $d(G)$, and independence number $\alpha(G)$.

Zitieren

Zitierform:

Harant, Jochen / Rautenbach, Dieter: Independence in connected graphs. 2009.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export