✦ LIBER ✦

Turán's theorem and k-connected graphs

✍ Scribed by Nicolas Bougard; Gwenaël Joret

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 167 KB
Volume: 58
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20289

No coin nor oath required. For personal study only.

✦ Synopsis

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 Valencia. In this article, we give a short proof of their result and determine the extremal graphs. We settle the case of 2‐connected graphs, characterize the corresponding extremal graphs, and also extend a result of Brouwer related to Turán's Theorem. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 1–13, 2008

📜 SIMILAR VOLUMES

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

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

Erdős–Turán Type Theorems on Qua

Erdő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 local structure theorem on 5-connected

A local structure theorem on 5-connected graphs

✍ Kiyoshi Ando 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 281 KB

## Abstract An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let __x__ be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from __x__ is two or less, then either there are two tri

Proof of Mader's conjecture on k-critica

Proof of Mader's conjecture on k-critical n-connected graphs

✍ Su Jianji 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 1 views

## Abstract Mader conjectured that every __k__‐critical __n__‐connected noncomplete graph __G__ has __2k__ + 2 pairwise disjoint fragments. The author in 9 proved that the conjecture holds if the order of __G__ is greater than (__k__ + 2)__n__. Now we settle this conjecture completely. © 2004 Wiley

Contractible Edges and Triangles in k-Co

Contractible Edges and Triangles in k-Connected Graphs

✍ Ken-ichi Kawarabayashi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 129 KB

It is proved that if G is a k-connected graph which does not contain K - 4 , then G has an edge e or a triangle T such that the graph obtained from G by connecting e or by contracting T is still k-connected. By using this theorem, we prove some theorems which are generalizations of earlier work. In