Turan's theorem and k-connected graphs

摘要

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 Turan'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 Turan's Theorem. (C) 2008 Wiley Periodicals, Inc.