A matching and a Hamiltonian cycle of the fourth power of a connected graph. (English) Zbl 0780.05046

Nebeský, Ladislav

Math. Bohem. 118, No. 1, 43-52 (1993).

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.

Reviewer: P.Sekanina (Fairbanks)

MSC:

05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45	Eulerian and Hamiltonian graphs
05C38	Paths and cycles
05C40	Connectivity

Keywords:

matching; factors; Hamiltonian cycles; powers of graphs; connected graph