Graphs with Unique Maximum Packing of Closed Neighborhoods

Abstract

A packing of a graph G is a subset P of the vertex set of G such that the closed neighborhoods of any two distinct vertices of P do not intersect. We study graphs with a unique packing of the maximum cardinality. We present several general properties for such graphs. These properties are used to characterize the trees with a unique maximum packing. Two characterizations are presented where one of them is inductive based on five operations.

Keywords

• unique maximum packing
• closed neighborhoods
• trees
• 05c70
• 05c05