Article

Full entry | PDF   (0.5 MB)
Keywords:
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

Partner of