Article
Full entry |
PDF
(0.6 MB)
Feedback
PDF
(0.6 MB)
Feedback
Keywords:
Hamiltonian cycle; power of connected graph; matching; powers of graphs; matching in graphs
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
Search
Partner of
