𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamilton Cycle Decomposition of Line Graphs and a Conjecture of Bermond

✍ Scribed by A. Muthusamy; P. Paulraja

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
614 KB
Volume
64
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper it is proved that if a graph (G) has a decomposition into an even (resp., odd) number of Hamilton cycles, then (L(G)), the line graph of (G), has a decomposition into Hamilton cycles (resp., Hamilton cycles and a 2-factor). Further, we show that if (G) is a (2 k)-regular graph having a Hamilton cycle, then (L(G)) has a decomposition into Hamilton cycles and a 2-factor. These results generalize a result of Jaeger and also support the following conjecture of Bermond: If (G) has a Hamilton cycle decomposition, then (L(G)) can be decomposed into Hamilton cycles. 1995 Academic Press. Inc

πŸ“œ SIMILAR VOLUMES

Hamilton decompositions of some line gra
Hamilton decompositions of some line graphs
✍ David A. Pike πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 361 KB

## Abstract The main result of this paper completely settles Bermond's conjecture for bipartite graphs of odd degree by proving that if __G__ is a bipartite (2__k__ + 1)‐regular graph that is Hamilton decomposable, then the line graph, __L__(__G__), of __G__ is also Hamilton decomposable. A similar

Decompositions of complete graphs into t
Decompositions of complete graphs into triangles and Hamilton cycles
✍ Darryn Bryant; Barbara Maenhaut πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 121 KB πŸ‘ 1 views

## Abstract For all odd integers __n__ β‰₯ 1, let __G~n~__ denote the complete graph of order __n__, and for all even integers __n__ β‰₯ 2 let __G~n~__ denote the complete graph of order __n__ with the edges of a 1‐factor removed. It is shown that for all non‐negative integers __h__ and __t__ and all p

Symmetric Hamilton cycle decompositions
Symmetric Hamilton cycle decompositions of the complete graph
✍ Jin Akiyama; Midori Kobayashi; Gisaku Nakamura πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 95 KB πŸ‘ 1 views

## Abstract We construct a new symmetric Hamilton cycle decomposition of the complete graph __K~n~__ for odd __n__ > 7. Β© 2003 Wiley Periodicals, Inc.

Symmetric Hamilton cycle decompositions
Symmetric Hamilton cycle decompositions of complete graphs minus a 1-factor
✍ Richard A. Brualdi; Michael W. Schroeder πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 190 KB πŸ‘ 1 views

Let n β‰₯ 2 be an integer. The complete graph K n with a 1-factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K n -F has a decomposition into Hamilton cycles which are symmetric with respect to the 1-factor F if and only if n ≑ 2,4 mod 8. We also show that