For a graph G and an integer r ≥ 1, G is r-EKR if no intersecting family of independent r-sets of G is larger than the largest star (a family of independent r-sets containing some fixed vertex in G), and G is strictly r-EKR if every extremal intersecting family of independent r-sets is a star. Recently, Hurlbert and Kamat gave a preliminary result about EKR property of ladder graphs. They showed that a ladder graph with n rungs is 3-EKR for all n ≥ 3. The present paper proves that this graph is r-EKR for all 1 ≤r ≤ n, and strictly r-EKR except for r = n - 1.
Yu-shuang LI, Hua-jun ZHANG
. Erdös-Ko-Rado Theorem for Ladder Graphs[J]. Acta Mathematicae Applicatae Sinica(English Series), 2014
, 30(3)
: 583
-588
.
DOI: 10.1007/s10255-014-0404-x
[1] Borg, P. Intersecting and cross-intersecting families of labelled sets. Electron. J. Combin., 15 (2008), N9
[2] Borg, P., Holroyd, F. The Erdös-Ko-Rado properties of various graphs containing singletons. Discrete Math., 309: 2877-2885 (2009)
[3] Deza, M., Frankl, P. Erdös-Ko-Rado theorem-22 years later. SIAM J. Alg. Disc. Methods, 4: 419-431 (1983)
[4] Erdös, P., Ko, C., Rado, R. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser., 2: 313-318 (1961)
[5] Holroyd, F.C., Spencer, C., Talbot, J. Compression and Erdös-Ko-Rado graphs. Discrete Math., 293: 155-164 (2005)
[6] Holroyd, F.C., Talbot, J. Graphs with the Erdös-Ko-Rado property. Discrete Math., 293: 165-176 (2005)
[7] Hurlbert, G., Kamat, V. Erdös-Ko-Rado theorems for chordal and bipartite graphs. arXiv:0903.4203vl [math.CO] 24 Mar 2009
