zbMATH — the first resource for mathematics

Existence of \(n\)-factors in powers of connected graphs. (English) Zbl 0735.05069
The author proves the following: If \(G\) is a connected graph of order \(p\geq n+1\) \((n\geq 1)\), with \(p\) odd if \(n\) is odd, then for any vertex \(v\) of \(G\), \(G^{n+1}-v\) has an \(n\)-factor. This supplements an earlier result of the author and Nebeský: If \(G\) is a connected graph of order \(p\geq n+1\) \((n\geq 1)\) with \(p\) even when \(n\) is odd, then \(G^{n+1}\) has an \(n\)-factor.
Actually the author derives the result by providing it for any spanning tree of \(G\). Besides the usual induction and case-studies, the proof technique involves a systematic ordering of the vertices in the different branches of the tree \(T\) at \(v\), going ’upwards’ from \(v\) to the leaves. This simplifies the distance computations.
Reviewer: K.R.Parthasarathy
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C12 Distance in graphs
05C05 Trees
PDF BibTeX Cite
Full Text: EuDML