Wissen, was gut ist. Studieren in Chemnitz.
Göring, Frank; Harant, Jochen; Rautenbach, Dieter; Schiermeyer, Ingo : Locally Dense Independent Sets in Regular Graphs of Large Girth

Göring, Frank ; Harant, Jochen ; Rautenbach, Dieter ; Schiermeyer, Ingo : Locally Dense Independent Sets in Regular Graphs of Large Girth

Author(s):
Göring, Frank
Harant, Jochen
Rautenbach, Dieter
Schiermeyer, Ingo
Title:
Locally Dense Independent Sets in Regular Graphs of Large Girth
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 19, 2007
Mathematics Subject Classification:
05C69 [ Dominating sets, independent sets, cliques ]
Abstract:
For an integer $d\geq 3$ let $\alpha(d)$ be the supremum over all $\alpha$ with the property that for every $\epsilon>0$ there exists some $g(\epsilon)$ such that every $d$-regular graph of order $n$ and girth at least $g(\epsilon)$ has an independent set of cardinality at least $(\alpha-\epsilon)n$. Extending an approach proposed by Lauer and Wormald (Large independent sets in regular graphs of large girth, {\it J. Comb. Theory, Ser. B} {\bf 97} (2007), 999-1009) and improving results due to Shearer (A note on the independence number of triangle-free graphs, II, {\it J. Comb. Theory, Ser. B} {\bf 53} (1991), 300-307) and Lauer and Wormald, we present the best known lower bounds for $\alpha(d)$ for all $d\geq 3$.
Keywords:
independence, regular graph, probabilistic method, girth, randomized algorithm
Language:
English
Publication time:
10 / 2007