Home » Subject » Graph Theory » Basic G.T.

Paths


Graph Theory » Basic G.T. » Paths

Decomposing a connected graph into paths. ★★★

Author(s): Gallai

Conjecture   Every simple connected graph on $ n $ vertices can be decomposed into at most $ \frac{1}{2}(n+1) $ paths.

Keywords:

Posted by fhavet
updated March 4th, 2013
add new comment
Graph Theory » Basic G.T. » Paths

Partition of a cubic 3-connected graphs into paths of length 2. ★★

Author(s): Kelmans

Problem   Does every $ 3 $-connected cubic graph on $ 3k $ vertices admit a partition into $ k $ paths of length $ 2 $?

Keywords:

Posted by fhavet
updated March 4th, 2013
add new comment

Note: Resolved problems from this section may be found in Solved problems.


Syndicate content