Turán's theorem for k-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

✍ 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)/(__

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 problems for integer-weighted grap

Turán problems for integer-weighted graphs

✍ Zoltán Füredi; André Kündgen 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

## Abstract A multigraph is (__k__,__r__)‐dense if every __k__‐set spans at most __r__ edges. What is the maximum number of edges ex~ℕ~(__n__,__k__,__r__) in a (__k__,__r__)‐dense multigraph on __n__ vertices? We determine the maximum possible weight of such graphs for almost all __k__ and __r__ (e

Turán theorems with repeated degrees

✍ Michael O. Albertson 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 352 KB

The maximum number of edges in a graph with no constant degree clique of a fixed size is determined asymptotically.

A Turán type problem for interval graphs

✍ Harvey Abbott; Meir Katchalski 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 313 KB

We consider the following analogue of a problem of Turin for interval graphs: Let c = c(n, rn) be the largest integer such that any interval graph with n vertices and at least m edges contains a complete subgraph on c vertices. We determine the value of c(n, m) explicitly.