Article ID Journal Published Year Pages File Type
4656208 Journal of Combinatorial Theory, Series A 2009 11 Pages PDF
Abstract

Let G be a graph consisting of powers of disjoint cycles and let A be an intersecting family of independent r-sets of vertices. Provided that G satisfies a further condition related to the clique numbers of the powers of the cycles, then |A| will be as large as possible if it consists of all independent r-sets containing one vertex from a specified cycle. Here r can take any value, 1⩽r⩽α(G), where α(G) is the independence number of G. This generalizes a theorem of Talbot dealing with the case when G consists of a cycle of order n raised to the power k. Talbot showed that .

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics