Open Packing in Graphs

Abstract

Let $G$ be a graph and let $S$ be a subset of vertices of $G$. The open neighborhood of a vertex $v$ of $G$ is the set of all vertices adjacent to $v$ in $G$. The set $S$ is an open packing of $G$ if the open neighborhoods of the vertices of $S$ are pairwise disjoint in $G$. The lower open packing number of $G$, denoted ${\rho }_L^o(G)$, is the minimum cardinality of a maximal open packing of $G$, while the (upper) open packing number of $G$, denoted ${\rho }^o(G)$, is the maximum cardinality among all open packings of $G$. In this paper, we present theoretical and computational
results for the open packing numbers of a graph.