Premium
Turán's theorem and k ‐connected graphs
Author(s) -
Bougard Nicolas,
Joret Gwenaël
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20289
Subject(s) - mathematics , combinatorics , extremal graph theory , stability theorem , discrete mathematics , graph , indifference graph , pathwidth , 1 planar graph , chordal graph , line graph , voltage graph , statistics , cauchy distribution
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