𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Turán's Theorem and Maximal Degrees

✍ Scribed by Béla Bollobás

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
89 KB
Volume
75
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

graphs of order n and size at least t r (n) that do not have a vertex x of maximal degree d x whose neighbours span at least t r&1 (d x )+1 edges. Furthermore, we show that, for every graph G of order n and size at least t r (n), the degree-greedy algorithm used by Bondy (1983, J. Combin. Theory Ser. B 34, 109 111) and Bolloba s and Thomason (1985, Ann. Discr. Math. 28, 47 97) constructs a complete graph K r+1 , unless G is the Tura n graph T r (n).

📜 SIMILAR VOLUMES

Turán's theorem and k-connected graphs
Turán's theorem and k-connected graphs
✍ Nicolas Bougard; Gwenaël Joret 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

## Abstract The minimum size of a __k__‐connected graph with given order and stability number is investigated. If no connectivity is required, the answer is given by Turán's Theorem. For connected graphs, the problem has been solved recently independently by Christophe et al., and by Gitler and Val

A generalization of Turán's theorem
A generalization of Turán's theorem
✍ Benny Sudakov; Tibor Szabó; H. Van Vu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## Abstract In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a __d__‐regular graph __G__ on __n__ vertices are sufficiently small, then the largest __K__~__t__~‐free subgraph of __G__ contains approximately (__t__ − 2)/(__

A weighted generalization of Tur�n's the
A weighted generalization of Tur�n's theorem
✍ Bondy, J. A.; Tuza, Zs. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 2 views

We obtain a generalization of Turán's theorem for graphs whose edges are assigned integer weights. We also characterize the extremal graphs in certain cases.

Erdős–Turán Type Theorems on Qua
Erdős–Turán Type Theorems on Quasiconformal Curves and Arcs
✍ Vladimir Andrievskii; Hans-Peter Blatt 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 210 KB

The theorems of Erdo s and Tura n mentioned in the title are concerned with the distribution of zeros of a monic polynomial with known uniform norm along the unit interval or the unit disk. Recently, Blatt and Grothmann (Const. Approx. 7 (1991), 19 47), Grothmann (``Interpolation Points and Zeros of

A Ramsey-type problem and the Turán numb
A Ramsey-type problem and the Turán numbers
✍ N. Alon; P. Erdős; D. S. Gunderson; M. Molloy 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

## Abstract For each __n__ and __k__, we examine bounds on the largest number __m__ so that for any __k__‐coloring of the edges of __K~n~__ there exists a copy of __K~m~__ whose edges receive at most __k−__1 colors. We show that for $k \ge \sqrt{n}\;+\,\Omega(n^{1/3})$, the largest value of __m__ i