Hamiltonian connectedness and a matching in powers of connected graphs

Abstract: In this paper the following results are proved: 1. Let $P_n$ be a path with $n$ vertices, where $n \geq5$ and $n \not= 7,8$. Let $M$ be a matching in $P_n$. Then $(P_n)^4 - M$ is hamiltonian-connected. 2. Let $G$ be a connected graph of order $p \geq5$, and let $M$ be a matching in $G$. Then $G^5 - M$ is hamiltonian-connected.

Keywords: power of a graph, matching, hamiltonian connectedness

Classification (MSC91): 05C70, 05C45

Full text of the article:

• Compressed Postscript file (148003 Bytes)