Decomposing graphs into long paths

Alexandr Kostochka; Vladimir Tashkinov

doi:10.1023/B:ORDE.0000026488.11602.7b

Decomposing graphs into long paths

Alexandr Kostochka
, Vladimir Tashkinov

Mathematics

Research output: Contribution to journal › Article › peer-review

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 C₃, C₄, C₅, and K₄ - e have no such decompositions. We construct an infinite sequence {F_i} _i=0^∞ (of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition.

Original language	English (US)
Pages (from-to)	239-253
Number of pages	15
Journal	Order
Volume	20
Issue number	3
DOIs	https://doi.org/10.1023/B:ORDE.0000026488.11602.7b
State	Published - 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

Online availability

10.1023/B:ORDE.0000026488.11602.7b

Library availability

Discover UIUC Full Text

Cite this

@article{0ada4c9ca35940e58c6e241e26182a5e,

title = "Decomposing graphs into long paths",

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.",

keywords = "2-edge-connected graphs, Edge-decompositions of graphs",

author = "Alexandr Kostochka and Vladimir Tashkinov",

note = "† This work was partially supported by the grants 02-01-00039 and 00-01-00916 of the Russian Foundation for Basic Research and the Dutch-Russian Grant NWO-047-008-006. ★ This material is based upon work supported by the National Science Foundation under Grant DMS-0099608. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.",

year = "2003",

doi = "10.1023/B:ORDE.0000026488.11602.7b",

language = "English (US)",

volume = "20",

pages = "239--253",

journal = "Order",

issn = "0167-8094",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Decomposing graphs into long paths

AU - Kostochka, Alexandr

AU - Tashkinov, Vladimir

N1 - † This work was partially supported by the grants 02-01-00039 and 00-01-00916 of the Russian Foundation for Basic Research and the Dutch-Russian Grant NWO-047-008-006. ★ This material is based upon work supported by the National Science Foundation under Grant DMS-0099608. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - 2-edge-connected graphs

KW - Edge-decompositions of graphs

UR - https://www.scopus.com/pages/publications/3543041317

UR - https://www.scopus.com/pages/publications/3543041317#tab=citedBy

U2 - 10.1023/B:ORDE.0000026488.11602.7b

DO - 10.1023/B:ORDE.0000026488.11602.7b

M3 - Article

AN - SCOPUS:3543041317

SN - 0167-8094

VL - 20

SP - 239

EP - 253

JO - Order

JF - Order

IS - 3

ER -

Decomposing graphs into long paths

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this