Packing 3-vertex paths in claw-free graphs and related topics

AbstractA Λ-factor of a graph G is a spanning subgraph of G whose every component is a 3-vertex path. Let v(G) be the number of vertices of G and γ(G) the domination number of G. A claw is a graph with four vertices and three edges incident to the same vertex. A graph is claw-free if it does not have an induced subgraph isomorphic to a claw. Our results include the following. Let G be a 3-connected claw-free graph, x∈V(G), e=xy∈E(G), and L a 3-vertex path in G. Then (a1) if v(G)≡0mod3, then G has a Λ-factor containing (avoiding) e, (a2) if v(G)≡1mod3, then G−x has a Λ-factor, (a3) if v(G)≡2mod3, then G−{x,y} has a Λ-factor, (a4) if v(G)≡0mod3 and G is either cubic or 4-connected, then G−L has a Λ-factor, (a5) if G is cubic with v(G)≥6 and E is a set of three edges in G, then G−E has a Λ-factor if and only if the subgraph induced by E in G is not a claw and not a triangle, (a6) if v(G)≡1mod3, then G−{v,e} has a Λ-factor for every vertex v and every edge e in G, (a7) if v(G)≡1mod3, then there exist a 4-vertex path Π and a claw Y in G such that G−Π and G−Y have Λ-factors, and (a8)γ(G)≤⌈v(G)/3⌉ and if in addition G is not a cycle and v(G)≡1mod3, then γ(G)≤⌊v(G)/3⌋. We also explore the relations between packing problems of a graph and its line graph to obtain some results on different types of packings and discuss relations between Λ-packing and domination problems