zbMATH — the first resource for mathematics

A matching and a Hamiltonian cycle of the fourth power of a connected graph. (English) Zbl 0780.05046
The author has improved his and Elena Wisztová’s former results which describe connections between matching, factors and Hamiltonian cycles in powers of graphs.
The main result of this paper says: If \(G\) is a connected graph of order \(\geq 4\) then for every matching \(M\) in \(G^ 4\) there exists a Hamiltonian cycle \(C\) of \(G^ 4\) such that \(E(C)\cap M=\varnothing\).
The proof uses a modification of techniques developed in former papers.
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C40 Connectivity
Full Text: EuDML