𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decompositions of highly connected graphs into paths of length 3

✍ Scribed by Carsten Thomassen

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
101 KB
Volume
58
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 graphs in general. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 286–292, 2008

📜 SIMILAR VOLUMES

Relative length of longest paths and cyc
Relative length of longest paths and cycles in 3-connected graphs
✍ Rao Li; Akira Saito; R.H. Schelp 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 2 views

## Abstract For a graph __G__, let __p(G)__ denote the order of a longest path in __G__ and __c(G)__ the order of a longest cycle in __G__, respectively. We show that if __G__ is a 3‐connected graph of order __n__ such that $\textstyle{\sum^{4}\_{i=1}\,{\rm deg}\_{G}\,x\_{i} \ge {3\over2}\,n + 1}$

Partitions of a graph into paths with pr
Partitions of a graph into paths with prescribed endvertices and lengths
✍ Hikoe Enomoto; Katsuhiro Ota 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 3 views

For a graph G, let ' 2 (G ) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| n i 1 k a i and ' 2 (G ) ! n k À 1, then for any k vertices v 1 , v 2 , F F F , v k in G, there exist vertex-disjoint paths P 1 , P 2 , F F F , P k such that |V (P i )| a i and v

Decomposition of the complete graph plus
Decomposition of the complete graph plus a 1-factor into cycles of equal length
✍ Mateja Šajna 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 354 KB 👁 1 views

## Abstract We determine the necessary and sufficient conditions for the existence of a decomposition of the complete graph of even order with a 1‐factor added into cycles of equal length. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 170–207, 2003; Published online in Wiley InterScience (www