Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 587.05032
Autor: Erdös, Paul; Pach, János
Title: Remarks on stars and independent sets. (In English)
Source: Aspects of topology, Mem. H. Dowker, Lond. Math. Soc. Lect. Note Ser. 93, 307-313 (1985).
Review: [For the entire collection see Zbl 546.00024.]
A graph G has property Ik if every set of k independent vertices have a common neighbour; G has property I if it has property Ik for all k. Pach, proving a conjecture of Erdös and Fajtolowicz, has shown that theorem 1: Every triangle-free graph on n vertices and having property I, contains a vertex of valency at least (n+1)/3; if 3|(n+1), this result is best possible. Lemma: If every set of \lceil log n\rceil independent vertices of a triangle-free graph on n vertices have a common neighbour, then the graph has property I. Sharpening theorem 1, the authors prove theorem 4: Every triangle-free graph on n vertices and with property I\lceil log n\rceil has a vertex of degree at least (n+1)/3.
Theorem 2: Let fr(n) denote the maximum integer such that every graph on n vertices having property I has a vertex of degree \geq f. Then fI(n) = (1+o(1))\frac{n log log n}{log n}.
Theorem 3. Let fI(r,n) denote the maximum integer f such that every Kr-free graph on n vertices having property I has a vertex of degree at least f. Then fI(w(n) log n,n) \leq (2+o(1))\frac{n log log w(n)}{log w(n)}, where w(n) is an arbitrary function tending to infinity.
Reviewer: W.G.Brown
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: extremal graph; independent vertices
Citations: Zbl 546.00024
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag