Induced H-packing k-partition of graphs

ABSTRACT

The minimum induced H-packing k-partition number is denoted by $ip{p}^{\mathcal{H}}(G,H)$. The induced H-packing k-partition number denoted by $ipp(G,H)$ is defined as $ipp(G,H)=\mathrm{m}\mathrm{i}\mathrm{n}ip{p}^{\mathcal{H}}(G,H)$ where the minimum is taken over all H-packings of G. In this paper, we obtain the induced $P_3$-packing k-partition number for trees, slim trees, split graphs, complete bipartite graphs, grids and circulant graphs. We also deal with networks having perfect $K_{1,3}$-packing where $K_{1,3}$ is a claw on four vertices. We prove that an induced $K_{1,3}$-packing k-partition problem is NP-Complete. Further we prove that the induced $K_{1,3}$-packing k-partition number of $Q^r$ is 2 for all hypercube networks with perfect $K_{1,3}$-packing and prove that $ipp\left(L{Q}^r\right)=4$ for all locally twisted cubes with perfect $K_{1,3}$-packing.

Keywords:

• induced $P_3$-packing k-partition of graphs
• induced $K_{13}$-packing k-partition of graphs
• NP-Complete
• hypercube networks
• Locally twisted cubes

2010 Mathematics Subject Classification:

• 05C70

Disclosure statement

No potential conflict of interest was reported by the author(s).