𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimum path decompositions of oriented cubic graphs

✍ Scribed by K. B. Reid; Keith Wayland

Publisher
John Wiley and Sons
Year
1987
Tongue
English
Weight
257 KB
Volume
11
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Pullman [3] conjectured that if k is an odd positive integer, then every orientation of a regular graph of degree k has a minimum decomposition which contains no vertex which is both the initial vertex of some path in the decomposition and the terminal vertex of some other path in the decomposition In this paper, the conjecture is established for cubic graphs, and its connection with Kelly's conjecture for tournaments is described A path decomposition of a directed graph D is a set of arc-disjoint directed paths such that the union of the arcs of these paths is the arc set of D . If M is a path decomposition of a directed graph D , M has k paths, and there does not exist a path dccomposition of D with less than k paths, then M is a minimum path decomposition of D .

Let u be a vertex of the directed graph D. and let M be a path decomposition of D . If u is the initial vertex of some path P in M and the terminal vertex of a second path R in M , then v is an eccentric vertex of M . A good decomposition of D is a path decomposition of D which contains no eccentric vertex.

The cardinality of a minimum path decomposition has been considered in several papers (see the references in [ 2 ] ) . In the present papsr, we answer the cubic case of the following conjecture of Pullman [3].

Conjecture.

Let k be an odd positive integer. Every orientation of a regular graph of degree k has a good decomposition.

📜 SIMILAR VOLUMES

Regular path decompositions of odd regul
Regular path decompositions of odd regular graphs
✍ Odile Favaron; François Genest; Mekkia Kouider 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract Kotzig asked in 1979 what are necessary and sufficient conditions for a __d__‐regular simple graph to admit a decomposition into paths of length __d__ for odd __d__>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable

A note on path and cycle decompositions
A note on path and cycle decompositions of graphs
✍ Dom Decaen 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

## Abstract In the study of decompositions of graphs into paths and cycles, the following questions have arisen: Is it true that every graph __G__ has a smallest path (resp. path‐cycle) decomposition __P__ such that every odd vertex of __G__ is the endpoint of exactly one path of __P__? This note g

Decompositions of highly connected graph
Decompositions of highly connected graphs into paths of length 3
✍ Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB 👁 1 views

## Abstract We prove that a 171‐edge‐connected graph has an edge‐decomposition into paths of length 3 if and only its size is divisible by 3. It is a long‐standing problem whether 2‐edge‐connectedness is sufficient for planar triangle‐free graphs, and whether 3‐edge‐connectedness suffices for graph