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
