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

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

Importance: Medium ✭✭
Author(s): Kelmans, Alexander K.
Subject: Graph Theory
» Basic Graph Theory
» » Paths
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 4th, 2013
Problem   Does every $ 3 $-connected cubic graph on $ 3k $ vertices admit a partition into $ k $ paths of length $ 2 $?

More generally, the following question is posed.

Problem   Does every $ 3 $-connected cubic graph on at least $ 3k $ vertices contain $ k $ pairwise vertex-disjoint paths of length $ 2 $?

In [K1], Kelmans gave a construction that provided infi nitely many 2-connected graphs for which the above statement is false.

Bibliography

[K1] Alexander K. Kelmans, Packing 3-vertex paths in 2-connected graphs

*[K2] Alexander K. Kelmans, On $ \Lambda $--Packing in 3--connected Graphs, RUTCOR Research Report 23--2005, Rutgers University. See also Packing 3-vertex Paths In Cubic 3-connected Graphs


* indicates original appearance(s) of problem.
add new comment