Hamilton decompositions of line graphs of some bipartite graphs

David A. Pike

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 3, page 303-310
  • ISSN: 2083-5892

Abstract

top
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).

How to cite

top

David A. Pike. "Hamilton decompositions of line graphs of some bipartite graphs." Discussiones Mathematicae Graph Theory 25.3 (2005): 303-310. <http://eudml.org/doc/270296>.

@article{DavidA2005,
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).},
author = {David A. Pike},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Hamilton cycles; graph decompositions; line graphs; Hamilton cycle},
language = {eng},
number = {3},
pages = {303-310},
title = {Hamilton decompositions of line graphs of some bipartite graphs},
url = {http://eudml.org/doc/270296},
volume = {25},
year = {2005},
}

TY - JOUR
AU - David A. Pike
TI - Hamilton decompositions of line graphs of some bipartite graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 3
SP - 303
EP - 310
AB - 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).
LA - eng
KW - Hamilton cycles; graph decompositions; line graphs; Hamilton cycle
UR - http://eudml.org/doc/270296
ER -

References

top
  1. [1] J.C. Bermond, Problem 97, Discrete Math. 71 (1988) 275, doi: 10.1016/0012-365X(88)90107-0. 
  2. [2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland Publishing Company, New York, 1979). Zbl1226.05083
  3. [3] K. Heinrich and H. Verrall, A Construction of a perfect set of Euler tours of K 2 k + 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 Zbl0914.05047
  4. [4] F. Jaeger, The 1-factorization of some line-graphs, Discrete Math. 46 (1983) 89-92, doi: 10.1016/0012-365X(83)90274-1. Zbl0523.05054
  5. [5] A. Kotzig, Z teorie konecných pravidelných grafov tretieho a stvrtého stupna, Casopis Pest. Mat. 82 (1957) 76-92. 
  6. [6] P. Martin, Cycles Hamiltoniens dans les graphes 4-réguliers 4-connexes, Aequationes Math. 14 (1976) 37-40, doi: 10.1007/BF01836203. Zbl0328.05118
  7. [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. Zbl0831.05056
  8. [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. Zbl0241.94037
  9. [9] D.A. Pike, Hamilton decompositions of some line graphs, J. Graph Theory 20 (1995) 473-479, doi: 10.1002/jgt.3190200411. Zbl0921.05049
  10. [10] D.A. Pike, Hamilton decompositions of line graphs of perfectly 1-factorisable graphs of even degree, Australasian J. Combin. 12 (1995) 291-294. Zbl0844.05073
  11. [11] H. Verrall, A Construction of a perfect set of Euler tours of K 2 k + 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 Zbl0911.05047
  12. [12] S. Zhan, Circuits and Cycle Decompositions (Ph.D. thesis, Simon Fraser University, 1992). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.