PDF

Discussiones Mathematicae Graph Theory 25(3) (2005) 303-310
DOI: https://doi.org/10.7151/dmgt.1283

HAMILTON DECOMPOSITIONS OF LINE GRAPHS OF SOME BIPARTITE GRAPHS

David A. Pike

Department of Mathematics and Statistics
Memorial University of Newfoundland
St. John's, Newfoundland, Canada, A1C 5S7

Abstract

Some bipartite Hamilton decomposable graphs that are regular of degree δ ≡ 2 (mod 4) are shown to have Hamilton decomposable line graphs. One consequence is that every bipartite Hamilton decomposable graph G with connectivity κ(G) = 2 has a Hamilton decomposable line graph L(G).

Keywords: Hamilton cycles, graph decompositions, line graphs.

2000 Mathematics Subject Classification: 05C70, 05C45.

References

[1]	J.C. Bermond, Problem 97, Discrete Math. 71 (1988) 275, doi: 10.1016/0012-365X(88)90107-0.
[2]	J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland Publishing Company, New York, 1979).
[3]	K. Heinrich and H. Verrall, A Construction of a perfect set of Euler tours of K2k+1, J. Combin. Designs 5 (1997) 215-230, doi: 10.1002/(SICI)1520-6610(1997)5:3<215::AID-JCD5>3.0.CO;2-I.
[4]	F. Jaeger, The 1-factorization of some line-graphs, Discrete Math. 46 (1983) 89-92, doi: 10.1016/0012-365X(83)90274-1.
[5]	A. Kotzig, Z teorie konecných pravidelných grafov tretieho a stvrtého stupna, Casopis Pest. Mat. 82 (1957) 76-92.
[6]	P. Martin, Cycles Hamiltoniens dans les graphes 4-réguliers 4-connexes, Aequationes Math. 14 (1976) 37-40, doi: 10.1007/BF01836203.
[7]	A. Muthusamy and P. Paulraja, Hamilton cycle decompositions of line graphs and a conjecture of Bermond, J. Combin. Theory (B) 64 (1995) 1-16, doi: 10.1006/jctb.1995.1024.
[8]	B.R. Myers, Hamiltonian factorization of the product of a complete graph with itself, Networks 2 (1972) 1-9, doi: 10.1002/net.3230020102.
[9]	D.A. Pike, Hamilton decompositions of some line graphs, J. Graph Theory 20 (1995) 473-479, doi: 10.1002/jgt.3190200411.
[10]	D.A. Pike, Hamilton decompositions of line graphs of perfectly 1-factorisable graphs of even degree, Australasian J. Combin. 12 (1995) 291-294.
[11]	H. Verrall, A Construction of a perfect set of Euler tours of K2k+I, J. Combin. Designs 6 (1998) 183-211, doi: 10.1002/(SICI)1520-6610(1998)6:3<183::AID-JCD2>3.0.CO;2-B.
[12]	S. Zhan, Circuits and Cycle Decompositions (Ph.D. thesis, Simon Fraser University, 1992).

Received 3 February 2004