Previous |  Up |  Next


Title: A matching and a Hamiltonian cycle of the fourth power of a connected graph (English)
Author: Nebeský, Ladislav
Language: English
Journal: Mathematica Bohemica
ISSN: 0862-7959 (print)
ISSN: 2464-7136 (online)
Volume: 118
Issue: 1
Year: 1993
Pages: 43-52
Summary lang: English
Category: math
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$. (English)
Keyword: matching
Keyword: factors
Keyword: Hamiltonian cycles
Keyword: powers of graphs
Keyword: connected graph
MSC: 05C38
MSC: 05C40
MSC: 05C45
MSC: 05C70
idZBL: Zbl 0780.05046
idMR: MR1213832
DOI: 10.21136/MB.1993.126012
Date available: 2009-09-24T20:57:08Z
Last updated: 2020-07-29
Stable URL:
Reference: [1] M. Behzad G. Chartrand, and L. Lesniak-Foster: Graphs & Digraphs.Prindle, Weber L Schmidt, Boston, 1979. MR 0525578
Reference: [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. MR 0321809, 10.1016/1385-7258(73)90007-3
Reference: [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
Reference: [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
Reference: [5] M. Sekanina: On an ordering of the set of vertices of a connected graph.Publ. Sci. Univ. Brno 412 (1960), 137-142. Zbl 0118.18903, MR 0140095
Reference: [6] D. P. Sumner: Graphs with 1-factors.Proc. Amer. Math. Soc. 42 (1974), 8-12. Zbl 0293.05157, MR 0323648
Reference: [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
Reference: [8] E. Wisztová: On a hamiltonian cycle of the fourth power of a connected graph.Mathematica Bohemica 116 (1991), 385-390. MR 1146396


Files Size Format View
MathBohem_118-1993-1_6.pdf 1.124Mb application/pdf View/Open
Back to standard record
Partner of
EuDML logo