𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A generalization of Turán's theorem

✍ Scribed by Benny Sudakov; Tibor Szabó; H. Van Vu

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
94 KB
Volume
49
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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)/(t − 1)‐fraction of its edges. Turán's theorem corresponds to the case d = n − 1. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

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.

Turán's Theorem and Maximal Degrees
Turán's Theorem and Maximal Degrees
✍ Béla Bollobás 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 89 KB

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

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

On a generalization of Rubin's theorem
On a generalization of Rubin's theorem
✍ Dmitry A. Shabanov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB

The work is devoted to the calculation of asymptotic value of the choice number of the complete r-partite graph K m \* r = K m,. ..,m with equal part size m. We obtained the asymptotics in the case ln r = o(ln m). The proof generalizes the classical result of A.L. Rubin for the case r = 2.