On factors of uniform intersection graphs (Q1196583)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On factors of uniform intersection graphs |
scientific article |
Statements
On factors of uniform intersection graphs (English)
0 references
16 January 1993
0 references
Let \(n,k,\lambda\) be integers satisfying \(0\leq\lambda<k<n\). The vertices of the uniform intersection graph \(G(n,k,\lambda)\) correspond to all \(k\)- element subsets of \(\{1,2,\dots,n\}\), and two vertices are adjacent whenever the intersection of the corresponding sets contains exactly \(\lambda\) elements. In this paper factors and factorizations of uniform intersection graphs are investigated. Using Petersen's classical result, the authors first show that \(G(n,k,\lambda)\) is 2-factorizable if either (a) \(k\) is even and \(\lambda\) is odd, or (b) \(n\) and \(k\) are both odd, while \(\lambda\) is even. Then 2-factors with all cycles having the same length in line graphs of complete graphs \(G(n,2,1)\) are searched. It turns out that \(G(n,2,1)\) has \({n\over 2}C_{n-1}\) as a factor if \(n\) is even, \({n-1\over 2}C_ n\) as a factor if \(n\) is odd, and \(nC_{(n-1)/2}\) as a factor if \(n\) is a prime number. Finally a factor consisting on some \(p\)-cycles and some isolated edges is presented in \(G(p,3,2)\) for prime \(p\geq 5\).
0 references
Kneser graphs
0 references
line graphs
0 references
factorizations
0 references
uniform intersection graphs
0 references
factor
0 references