Article
Full entry |
PDF
(1.1 MB)
Feedback
PDF
(1.1 MB)
Feedback
Keywords:
matching; factors; Hamiltonian cycles; powers of graphs; connected graph
matching; factors; Hamiltonian cycles; powers of graphs; connected graph
Summary:
The following result is proved: Let $G$ be a connected graph of order $geq 4$. Then for every matching $M$ in $G^4$ there exists a hamiltonian cycle $C$ of $G^4$ such that $E(C)\bigcap M=0$.
References:
[1] M. Behzad G. Chartrand, and L. Lesniak-Foster: Graphs & Digraphs. Prindle, Weber L Schmidt, Boston, 1979. MR 0525578
[2] G. Chartrand A. D. PoUmeni, and M. J. Stewart: The existence of 1-factors in line graphs, squares and total graphs. Indag. Math. 35 (1973), 228-232. DOI 10.1016/1385-7258(73)90007-3 | MR 0321809
[3] L. Nebeský: On the existence of a 3-factor in the fourth power of graph. Časopis pěst. mat. 105 (1980), 204-207. MR 0573113
[4] L. Nebeský: On a 1-factor of the fourth power of a connected graph. Časopis pěst. mat. 113 (1988), 415-420. MR 0981882
[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] D. P. Sumner: Graphs with 1-factors. Proc. Amer. Math. Soc. 42 (1974), 8-12. MR 0323648 | Zbl 0293.05157
[7] E. Wisztová: A hamiltonian cycle and a 1-factor on the fourth power of a graph. Časopis pěst. mat. 110 (1985), 403-412. MR 0820332
[8] 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
