On Rooted Packings, Decompositions, and Factors of Graphs

In this article, we study so‐called rooted packings of rooted graphs. This concept is a mutual generalization of the concepts of a vertex packing and an edge packing of a graph. A rooted graph is a pair ( G , T ) , where G is a graph and T ⊆ V ( G ) . Two rooted graphs ( G , T ) and ( H , S ) are isomorphic if there is an isomorphism of the graphs G and H such that S is the image of T in this isomorphism. A rooted graph ( H , S ) is a rooted subgraph of a rooted graph ( G , T ) if H is a subgraph of G and S ⊆ T . By a rooted ( H , S ) ‐packing into a rooted graph ( G , T ) we mean a collection( H 1 , S 1 ) , ( H 2 , S 2 ) , ... , ( H p , S p )of rooted subgraphs of ( G , T ) isomorphic to ( H , S ) such that the sets of edges E ( H 1 ) , E ( H 2 ) , ... , E ( H p )are pairwise disjoint and the setsS 1 , S 2 , ... , S pare pairwise disjoint. In this article, we concentrate on studying maximum ( H , S ) ‐packings when H is a star. We give a complete classification with respect to the computational complexity status of the problems of finding a maximum ( H , S ) ‐packing of a rooted graph when H is a star. The most interesting polynomial case is the case when H is the 2‐edge star and S contains the center of the star only. We prove a min–max theorem for ( H , S ) ‐packings in this case.