Packing 3-vertex paths in cubic 3-connected graphs

Details Packing 3-vertex paths in cubic 3-connected graphs Packing 3-vertex paths in cubic 3-connected graphs

2008-01-08

arxiv.org/abs/0801.1239v1

Mathematics

Combinatorics

24 pages and 11 figures

Scientific paper

Let v(G) and p(G) be the number of vertices and the maximum number of disjoint 3-vertex paths in G, respectively. We discuss the following old Problem: Is the following claim (P) true ? (P) if G is a 3-connected and cubic graph, then p(G) = [v(G)/3], where [v(G)/3] is the floor of v(G)/3. We show, in particular, that claim (P) is equivalent to some seemingly stronger claims. It follows that if claim (P) is true, then Reed's dominating graph conjecture (see [14]) is true for cubic 3-connected graphs.

Affiliated with

Also associated with

No associations

Rating

Packing 3-vertex paths in cubic 3-connected graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Packing 3-vertex paths in cubic 3-connected graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packing 3-vertex paths in cubic 3-connected graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-421445