Decomposing Graphs into Long Paths |
| |
| Authors: | Kostochka Alexandr Tashkinov Vladimir |
| |
| Institution: | (1) University of Illinois, Urbana, s, IL 61801, USA;(2) Institute of Mathematics, Novosibirsk, 630090, Russia;(3) Institute of Mathematics, Novosibirsk, 630090, Russia |
| |
| 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
3, C
4, C
5, and K
4−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.
This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
| Keywords: | edge-decompositions of graphs 2-edge-connected graphs |
| 本文献已被 SpringerLink 等数据库收录！ |
|
