Geodesic
Perfect Set of Euler Tours of Kp,p,p
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 783-796.

Voir la notice de l'article provenant de la source Library of Science

Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G, is Hamilton cycle decomposable. In this paper, we construct a perfect set of Euler tours for the complete tripartite graph Kp,p,p for any prime p and hence prove Bermond’s conjecture for G = Kp,p,p.
Keywords: compatible Euler tour, line graph, Hamilton cycle decomposition 
@article{DMGT_2016_36_4_a0,
     author = {Govindan, T. and Muthusamy, A.},
     title = {Perfect {Set} of {Euler} {Tours} of {K\protect\textsubscript{p,p,p}}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {783--796},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a0/}
}
TY  - JOUR
AU  - Govindan, T.
AU  - Muthusamy, A.
TI  - Perfect Set of Euler Tours of Kp,p,p
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 783
EP  - 796
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a0/
LA  - en
ID  - DMGT_2016_36_4_a0
ER  - 
%0 Journal Article
%A Govindan, T.
%A Muthusamy, A.
%T Perfect Set of Euler Tours of Kp,p,p
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 783-796
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a0/
%G en
%F DMGT_2016_36_4_a0
Govindan, T.; Muthusamy, A. Perfect Set of Euler Tours of Kp,p,p. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 783-796. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a0/

[1] J.-C. Bermond, Research Problems. Problem 97, Discrete Math. 71 (1988) 275-276. doi: 10.1016/0012-365X(88)90107-0

[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan, New York, 1976).

[3] T. Govindan and A. Muthusamy, Nonexistence of a pair of arc disjoint directed Hamilton cycles on line digraphs of 2-diregular digraphs, Discrete Math. Algorithms Appl. 07 (2015). doi: 10.1142/S1793830915500342

[4] K. Heinrich and H. Verrall, A construction of a perfect set of Euler tours of K2k+1, J. Combin. Des. 5 (1997) 215-230. doi: 10.1002/(SICI)1520-6610(1997)5:3h215::AID-JCD5i3.0.CO;2-I

[5] A. Muthusamy and P. Paulraja, Hamilton cycle decomposition of line graphs and a conjecture of Bermond, J. Combin. Theory Ser. B 64 (1995) 1-16. doi: 10.1006/jctb.1995.1024

[6] D.A. Pike, Hamilton decompositions of some line graphs, J. Graph Theory 20 (1995) 473-479. doi: 10.1002/jgt.3190200411

[7] D.A. Pike, Hamilton decompositions of line graphs of perfectly 1-factorisable graphs of even degree, Australas. J. Combin. 12 (1995) 291-294.

[8] S. Zhan, Circuits and cycle decompositions (Ph.D. Thesis, Simon Fraser University, 1992).

[9] H. Verrall, A construction of a perfect set of Euler tours of K2k + I, J. Combin. Des. 6 (1998) 183-211. doi: 10.1002/(SICI)1520-6610(1998)6:3h183::AID-JCD2i3.0.CO;2-B