The packing number and Laplacian spectrum of a graph

Abstract

For a subgraph H of G, an H-packing of G is a set of pairwise disjoint subgraphs that are all isomorphic copies of H. An H-packing of maximum cardinality is a maximum H-packing in G denoted by ζ_H(G). The cardinality of a maximum H-packing of G is called its H-packing number denoted by θ_H(G), and a maximum H-packing is perfect if |V(G)|=|V(H)|·θ_H(G). In this paper, we give a necessary and sufficient condition of ζ_H(G) for a perfect H-packing of G whenever G is a tree. Moreover, we show that is a lower bound for the number of Laplacian eigenvalues of G exceeding r, where K_{1, r−1} (r≥2) is a star.

Keywords:

• graph
• packing number
• Laplacian spectrum
• perfect subgraph
• lower bound

2010 AMS Subject Classification::

• 05C50

Acknowledgements

The authors are grateful to the anonymous referees for their valuable comments and suggestions, which led to an improvement of the original manuscript. This work is supported by NSFC Grant No. 11261059.