| 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:
|
http://hdl.handle.net/10338.dmlcz/126012 |
| . |
| 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 |
| . |
