Decomposing graphs into long paths

Alexandr Kostochka, Vladimir Tashkinov

Research output: Contribution to journalArticle

Abstract

It is known that the edge set of a 2-edge-connected 3-regular graph can be decomposed into paths of length 3. W. Li asked whether the edge set of every 2-edge-connected graph can be decomposed into paths of length at least 3. The graphs C3, C4, C5, and K4 - e have no such decompositions. We construct an infinite sequence {Fi} i=0 (of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition.

Original languageEnglish (US)
Pages (from-to)239-253
Number of pages15
JournalOrder
Volume20
Issue number3
DOIs
StatePublished - Dec 1 2003

Keywords

  • 2-edge-connected graphs
  • Edge-decompositions of graphs

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Decomposing graphs into long paths'. Together they form a unique fingerprint.

  • Cite this