Locally dense independent sets in regular graphs of large girth

Göring, Frank; Harant, Jochen GND; Rautenbach, Dieter GND; Schiermeyer, Ingo GND

For an integer d 3 let (d) be the supremum over all with the property that for every > 0 there exists some g() such that every d-regular graph of order n and y girth at least g() has an independent set of cardinality at least ( − )n. Extending an approach proposed by Lauer and Wormald (Large independent sets in regular graphs of large girth, J. Comb. Theory, Ser. B 97 (2007), 999-1009) and improving results due to Shearer (A note on the independence number of triangle-free graphs, II, J. Comb. Theory, Ser. B 53 (1991), 300-307) and Lauer and Wormald, we present the best known lower bounds for (d) for all d 3.

Zitieren

Zitierform:

Göring, Frank / Harant, Jochen / Rautenbach, Dieter / et al: Locally dense independent sets in regular graphs of large girth. 2007.

Zugriffsstatistik

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

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export