A generalization of Talbot's theorem about King Arthur and his Knights of the Round Table |
| |
Authors: | AJW Hilton CL Spencer |
| |
Institution: | a School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, UK b Department of Mathematics, University of Reading, Whiteknights, Reading RG6 6AX, UK |
| |
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 . |
| |
Keywords: | Finite sets Erdö s-Ko-Rado Intersection theorem Cycles Graph theory Independent sets King Arthur Round Table |
本文献已被 ScienceDirect 等数据库收录! |
|