Packing in trees Original Research Article

Let G be a graph and let v be a vertex of G. The open neighbourhood N(v) of v is the set of all vertices adjacent with v in G, while the closed neighbourhood of v is N(v) ∪ (v). A packing of a graph G is a set of vertices whose closed neighbourhoods are pairwise disjoint. Equivalently, a packing of a graph G is a set of vertices whose elements are pairwise at distance at least 3 apart in G. The lower packing number of G, denoted ϱL(G), is the minimum cardinality of a maximal packing of G while the (upper) packing number of G, denoted ϱ(G), is the maximum cardinality among all packings of G. An open packing of G is a set of vertices whose open neighbourhoods are pairwise disjoint. The lower open packing number of G, denoted ϱL0(G), is the minimum cardinality of a maximal open packing of G while the (upper) open packing number of G, denoted ϱ0(G), is the maximum cardinality among all open packings of G. We present upper bounds on the packing number and the lower packing number of a tree. Bounds relating the packing numbers and open packing numbers of a tree are established.