Closure, stability and iterated line graphs with a 2-factor (Q1044973): Difference between revisions

The present paper concentrates on the problem of the existence of a 2-factor with at most \(k\) components in iterated line graph. The line \(n\)-iterated graph \(L^n(G)\) is defined recursively as \(L^n(G)=L( L^{n-1}(G))\) where \(L\) is the line operator. This problem is a generalization of the problem of existence of a Hamiltonian cycle in \(L^n(G)\) as for \(k=1\), a 2-factor is a Hamiltonian cycle. It is proved that \(L^n(G)\) has a \(2\)-factor with at most \(k\) components if and only if \(G\) contains a subgraph from the special class of graphs defined in this paper. The authors also prove the stability of the number \(k\) of components with respect to the closure operator for claw-free graphs. It is proved that if \(G\) is a claw-free graph than \(L^n(G)\) has a \(2\)-factor with at most \(k\) components if and only if \(L^n(cl(G))\) has such a factor. The closure operator is defined as recursively repeated local completion of neighborhoods of vertices in \(G\).