Packing in regular graphs |
| |
Authors: | Michael A. Henning |
| |
Affiliation: | Department of Pure and Applied Mathematics, University of Johannesburg, South Africa. E-Mail mahenning@uj.ac.za |
| |
Abstract: | A set S of vertices in a graph G is a packing if the vertices in S are pairwise at distance at least 3 apart in G. The packing number of G, denoted by ρ(G), is the maximum cardinality of a packing in G. Favaron [Discrete Math. 158 (1996), 287–293] showed that if G is a connected cubic graph of order n different from the Petersen graph, then ρ(G) ≥ n/8. In this paper, we generalize Favaron’s result. We show that for k ≥ 3, if G is a connected k-regular graph of order n that is not a diameter-2 Moore graph, then ρ(G) ≥ n/(k2 ? 1). |
| |
Keywords: | 05C65 |
|
|