On normal partitions in cubic graphs
Jean-Luc Fouquet ; Jean-Marie Vanherpe
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 293-312 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

A normal partition of the edges of a cubic graph is a partition into trails (no repeated edge) such that each vertex is the end vertex of exactly one trail of the partition. We investigate this notion and give some results and problems.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:270604 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1448,
     author = {Jean-Luc Fouquet and Jean-Marie Vanherpe},
     title = {On normal partitions in cubic graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {293-312},
     zbl = {1194.05123},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1448}
}

Jean-Luc Fouquet; Jean-Marie Vanherpe. On normal partitions in cubic graphs. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 293-312. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1448/

[000] [1] J.A. Bondy, Basic graph theory: Paths and circuits, in: M. Grötschel, R.L. Graham and L. Lovász, eds, Handbook of Combinatorics, vol. 1, pages 3-112 (Elsevier, North-Holland, 1995). | Zbl 0849.05044

[001] [2] A. Bouchet and J.L. Fouquet, Trois types de décompositions d'un graphe chaînes, Annals of Discrete Math. 17 (1983) 131-141. | Zbl 0537.05052

[002] [3] G. Fan and A. Raspaud, Fulkerson's conjecture and circuit covers, J. Combin. Theory (B) 61 (1994) 133-138, doi: 10.1006/jctb.1994.1039. | Zbl 0811.05053

[003] [4] L. Goddyn, Cones, lattices and Hilbert base of circuits and perfect matching, in: N. Robertson and P. Seymour, eds, Graph Structure Theory, Contemporary Mathematics Volume 147, pages 419-439 (American Mathematical Society, 1993), doi: 10.1090/conm/147/01189.

[004] [5] R. Halin, A theorem on n-connected graphs, J. Combin. Theory (1969) 150-154. | Zbl 0172.25803

[005] [6] J.M. Vanherpe, J.L. Fouquet, H. Thuillier and A.P. Wojda, On odd and semi-odd linear partitions of cubic graphs, preprint, 2006. | Zbl 1193.05130

[006] [7] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916) 453-465, doi: 10.1007/BF01456961.

[007] [8] A. Kotzig, Moves without forbidden transitions, Mat.-Fyz. Casopis 18 (1968) 76-80, MR 39#4038. | Zbl 0155.31901

[008] [9] H. Li, Perfect path double covers in every simple graphs, J. Graph. Theory 14 (1990) 645-650, MR 91h#05052. | Zbl 0725.05054

[009] [10] P. Seymour, On multi-colourings of cubic graphs and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. (3) 38 (1979) 423-460, doi: 10.1112/plms/s3-38.3.423. | Zbl 0411.05037