Mathematics – Combinatorics
Scientific paper
2009-10-15
Mathematics
Combinatorics
29 pages and 9 figures. Accepted for publication in Discrete Mathematics in August 14, 2009
Scientific paper
A subgraph (a spanning subgraph) of a graph G whose all components are 3-vertex paths is called an L-packing (respectively, an L-factor} of G. We discuss the following old PROBLEM (A. Kelmans, 1984). Is the following claim true? (C) If G is a cubic 3-connected graph, then G has an L-packing that avoids at most two vertices of G. We show, in particular, that claim (C) is equivalent to some seemingly stronger claims (see Theorem 3.1 below). For example, if G is a cubic 3-connected graph and the number of vertices of G is divisible by three, then then the following claims are equivalent: G has an L-factor, for every edge e of G there is an L-factor of G avoiding (containing) e, G - {e,f} has an L-factor for every two edges e and f of G, and G - P has an L-factor for every 3-vertex path P in G. It follows that if claim (C) is true, then Reed's dominating graph conjecture is true for cubic 3-connected graphs. We also show that certain claims in Theorem 3.1 are best possible. We give a construction providing infinitely many cyclically 6-connected graphs G with two disjoint 3-vertex paths P and P' such that the number of vertices of G is divisible by three and G - P- P' has no L-factor. Keywords: cubic 3-connected graph, 3-vertex path packing, 3-vertex path factor, domination.
Kelmans Alexander
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-617694