On \(k\)-packings of Graphs

A set \(\mathcal{P} \subseteq V(G)\) is a \(k\)-packing of a graph \(G\) if for every pair of vertices \(u,v \in P\), \(d(u,v) \geq k+1\). We define a graph \(G\) to be \(k\)-equipackable if every maximal \(k\)-packing of \(G\) has the same size. In this paper, we construct, for \(k \leq 1\), an infinite family \(\mathcal{F}_k\) of \(k\)-equipackable graphs, recognizable in polynomial time. We prove further that for graphs of girth at least \(4k+4\), every \(k\)-equipackable graph is a member of \(\mathcal{F}_k\).