Independence, odd girth, and average degree

Löwenstein, Christian; Pedersen, Anders Sune; Rautenbach, Dieter GND; Regen, Friedrich GND

We prove several best-possible lower bounds in terms of the order and the average degree for the independence number of graphs which are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle-free graphs of maximum degree at most $3$ due to Heckman and Thomas [A New Proof of the Independence Ratio of Triangle-Free Cubic Graphs, {\it Discrete Math.} {\bf 233} (2001), 233-237] to arbitrary triangle-free graphs. For connected triangle-free graphs of order $n$ and size $m$, our result implies the existence of an independent set of order at least $(4n-m-1)/7$.

Cite

Citation style:

Löwenstein, Christian / Pedersen, Anders Sune / Rautenbach, Dieter / et al: Independence, odd girth, and average degree. 2009.

Access Statistic

Total:
Downloads:
Abtractviews:
Last 12 Month:
Downloads:
Abtractviews:

open graphic

Rights

Use and reproduction:
All rights reserved

Export