Packing (2ᵏ⁺¹-1)-order perfect binary trees into (k+1)-connected graph

Original · EN

Let G=(V,E) and H be two graphs. Packing problem is to find in G the largest number of independent subgraphs each of which is isomorphic to H. Let U⊂V. If the graph G-U has no subgraph isomorphic to H, U is a cover of G. Covering problem is to find the smallest set U. The vertex-disjoint tree packing was not sufficiently discussed in literature but has its applications in data encryption and in communication networks such as multi-cast routing protocol design. In this paper, we give the kind of (k+1)-connected graph G' into which we can pack independently the subgraphs that are each isomorphic to the (2ᵏ⁺¹-1)-order perfect binary tree Tₖ. We prove that in G' the largest number of vertex-disjoint subgraphs isomorphic to Tₖ is equal to the smallest number of vertices that cover all subgraphs isomorphic to Tₖ. Then, we propose that Tₖ does not have the Erdős-Pósa property. We also prove that the Tₖ packing problem in an arbitrary graph is NP-hard, and propose the distributed approximation algorithms.