The packing number and Laplacian spectrum of a graph

摘要

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 θ_(k_(1,r-1)) (G) is a lower bound for the number of Laplacian eigenvalues of G exceeding r, where K_(1,r-1) (r ≥ 2) is a star.