On normal partitions in cubic graphs

• Autorzy: Jean-Luc Fouquet , Jean-Marie Vanherpe
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cubic graph; edge-partition

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2009
• Tom: 29
• Numer: 2
• Strony: 293-312

Daty

wydano

2009

otrzymano

2007-12-03

poprawiono

2008-06-20

zaakceptowano

2008-12-17

Twórcy

autor

Jean-Luc Fouquet

• L.I.F.O., Faculté des Sciences, B.P. 6759, Université d'Orléans, 45067 Orléans Cedex 2, France

autor

Jean-Marie Vanherpe

• L.I.F.O., Faculté des Sciences, B.P. 6759, Université d'Orléans, 45067 Orléans Cedex 2, France

Bibliografia

• [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).
• [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.
• [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.
• [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.
• [5] R. Halin, A theorem on n-connected graphs, J. Combin. Theory (1969) 150-154.
• [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.
• [7] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916) 453-465, doi: 10.1007/BF01456961.
• [8] A. Kotzig, Moves without forbidden transitions, Mat.-Fyz. Casopis 18 (1968) 76-80, MR 39#4038.
• [9] H. Li, Perfect path double covers in every simple graphs, J. Graph. Theory 14 (1990) 645-650, MR 91h#05052.
• [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.

Identyfikatory

DOI

10.7151/dmgt.1448