# Article

Full entry | PDF   (0.6 MB)
Keywords:
Hamiltonian cycle; power of connected graph; matching; powers of graphs; matching in graphs
Summary:
In this paper the following theorem is proved: Let \$G\$ be a connected graph of order \$p\geq 4\$ and let \$M\$ be a matching in \$G\$. Then there exists a hamiltonian cycle \$C\$ of \$G^4\$ such that \$E(C)\bigcap M=0\$.
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ý: On the existence of a 3-factor in the fourth power of a graph. Čas. pěst. mat. 105 (1980), 204-207. MR 0573113
[4] L. Nebeský: Edge-disjoint 1-factors in powers of connected graphs. Czech. Math. J. 34 (109) (1984), 499-505. MR 0764434
[5] L. Nebeský: On a 1-factor of the fourth power of a connected graph. Čas. pěst. mat. 113 (1988), 415-420. MR 0981882
[6] J. Sedláček: Introduction into the Graph Theory. (Czech). Academia nakl. ČSAV, Praha 1981.
[7] E. Wisztová: A hamiltonian cycle and a 1-factor in the fourth power of a graph. Čas. pěst. mat. 110 (1985), 403-412. MR 0820332

Partner of