Home » Subject » Graph Theory » Basic G.T. » Cycles
Importance: Medium ✭✭
Author(s): Sabidussi, Gert
Subject: Graph Theory
» Basic Graph Theory
» » Cycles
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 4th, 2013
Conjecture   Let $ G $ be an eulerian graph of minimum degree $ 4 $, and let $ W $ be an eulerian tour of $ G $. Then $ G $ admits a decomposition into cycles none of which contains two consecutive edges of $ W $.

Kotzig proved the converse statement:

Theorem   Let $ G $ be an eulerian graph of minimum degree $ 4 $ and let $ (C_1, \dots , C_p) $ be a decomposition into cycles of $ G $. Then $ G $ admits an eulerian tour such that none of the $ C_i $, $ 1\leq i\leq p $, contains two consecutive edges of $ W $.

For more details on eulerian graphs, see [F].

Bibliography

*[F] H. Fleischner. Eulerian Graphs and Related Topics. Part 1. Vol. 1. Annals of Discrete Mathematics, Vol. 45, (1990) North-Holland, Amsterdam.


* indicates original appearance(s) of problem.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options