# 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
##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C12 Distance in graphs 05C05 Trees
##### Keywords:
$$n$$-factor
Full Text: