Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656208 | Journal of Combinatorial Theory, Series A | 2009 | 11 Pages |
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