Packing in trees

✍ Scribed by Michael A. Henning

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 532 KB
• Volume: 186
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00228-8

✦ Synopsis

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) U {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 pL(G), is the minimum cardinality of a maximal packing of G while the (upper) packing number of G, denoted p(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 p~(G), is the minimum cardinality of a maximal open packing of G while the (upper) open packing number of G, denoted p°(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.