✦ LIBER ✦

A note on path and cycle decompositions of graphs

✍ Scribed by Dom Decaen

Publisher: John Wiley and Sons
Year: 1981
Tongue: English
Weight: 137 KB
Volume: 5
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190050212

No coin nor oath required. For personal study only.

✦ Synopsis

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 gives a negative answer to both questions.

📜 SIMILAR VOLUMES

Minimum path decompositions of oriented

Minimum path decompositions of oriented cubic graphs

✍ K. B. Reid; Keith Wayland 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 1 views

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

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 shortest cycle covers of cubic

A note on shortest cycle covers of cubic graphs

✍ Xinmin Hou; Cun-Quan Zhang 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB 👁 1 views

## Abstract Let __SCC__~3~(__G__) be the length of a shortest 3‐cycle cover of a bridgeless cubic graph __G__. It is proved in this note that if __G__ contains no circuit of length 5 (an improvement of Jackson's (__JCTB 1994__) result: if __G__ has girth at least 7) and if all 5‐circuits of __G_

Note on graphs without repeated cycle le

Note on graphs without repeated cycle lengths

✍ Chen, Guantao; Lehel, Jen�; Jacobson, Michael S.; Shreve, Warren E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB 👁 1 views

In this note we prove that every 2-connected graph of order n with no repeated cycle lengths has at most n + 2(n -2) -1 edges and we show this result is best possible with the correct order of magnitude on √ n. The 2connected case is also used to give a quick proof of Lai's result on the general cas

A Note on Alternating Cycles in Edge-Col

A Note on Alternating Cycles in Edge-Coloured Graphs

✍ Anders Yeo 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 431 KB

Grossman and Ha ggkvist gave a sufficient condition under which a two-edgecoloured graph must have an alternating cycle (i.e., a cycle in which no two consecutive edges have the same colour). We extend their result to edge-coloured graphs with any number of colours. That is, we show that if there is

Symmetric Hamilton cycle decompositions

Symmetric Hamilton cycle decompositions of complete graphs minus a 1-factor

✍ Richard A. Brualdi; Michael W. Schroeder 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 1 views

Let n ≥ 2 be an integer. The complete graph K n with a 1-factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K n -F has a decomposition into Hamilton cycles which are symmetric with respect to the 1-factor F if and only if n ≡ 2,4 mod 8. We also show that