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

A A-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 gamma(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 epsilon V(C), e = xy epsilon E(G), and L a 3-vertex path in G. Then (a1) if v(G) 0 mod 3, then G has a A-factor containing (avoiding) e, (a2) if v(G) 1 mod 3, then G - x has a A-factor, (a3) if v(G) 2 mod 3, then G - {x, y} has a A-factor, (a4) if v(G) 0 mod 3 and G is either cubic or 4-connected, then G - L has a 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 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) 1 mod 3, then G - {v, e} has a A-factor for every vertex v and every edge e in G, (a7) if v(G) 1 mod 3, then there exist a 4-vertex path Pi and a claw Y in G such that G-Pi and G-Y have A-factors, and (a8)y(G) <= (inverted right perpendicular) v(G)/3(inverted left perpendicular) and if in addition G is not a cycle and v(G) 1 mod 3, then gamma(G) <= (left perpendicular)v(G)/ 3(right perpendicular). 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 A-packing and domination problems. Published by Elsevier B.V.