Article
Full entry |
PDF
(0.6 MB)
Feedback
PDF
(0.6 MB)
Feedback
Keywords:
power; distance; matching; hamiltonian path; hamiltonian connected; power of a graph
power; distance; matching; hamiltonian path; hamiltonian connected; power of a graph
Summary:
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.
References:
[1] M. Behzad G. Chartrand L. Lesniak-Foster: Graphs & Digraphs. Prindle, Weber & Schmidt, Boston 1979. MR 0525578
[2] F. Harary: Graph Theory. Addison-Wesley, Reading (Mass.), 1969. MR 0256911 | Zbl 0196.27202
[3] L. Nebeský: A matching and a hamiltonian cycle of the fourth power of a connected graph. Mathematica Bohemica 118 (1993), 43-52. MR 1213832
[4] J. Sedláček: Introduction Into the Graph Theory. Academia, Praha, 1981. (In Czech.)
[5] M. Sekanina: On an ordering of the set of vertices of a connected graph. Publ. Sci. Univ. Brno 412 (1960), 137-142. MR 0140095 | Zbl 0118.18903
[6] E. Wisztová: On a hamiltonian cycle of the fourth power of a connected graph. Mathematica Bohemica 116 (1991), 385-390. MR 1146396
Search
Partner of
