Neighborhoods in Maximum Packings of $2K_n$ with Triples

Abstract

In this paper, we use a recent result of Bryant, Horsley, and Pettersson in [1] to provide an alternate and more straightforward proof of results concerning neighborhood graphs in maximum packings of $2K_n$ with triples, some of which were only recently obtained.

To set the stage, consider any partial triple system $(V,B)$ of $2K_n$. In this system, the neighborhood of a vertex $v$ is defined as the subgraph induced by the set $\{\{x,y\}\mid \{v,x,y\}\in B\}$. This concept plays a crucial role in the results initially obtained by Colbourn and Rosa for $n\equiv 0,1(\mathrm{mod}3)$ and by Chaffee and Rodger for $n\equiv 2(\mathrm{mod}3)$. These results offer a complete characterization of the possible neighborhoods in a maximum packing of $2K_n$.

In both of these original papers, the authors employed difference methods—a combinatorial technique that often involves selecting pairs of elements from a group and studying their differences—and a pull-up technique, which is used to modify the neighborhood of a vertex. However, despite the effectiveness of these methods, neither approach seems to lend itself easily to deriving the results of the other.

In our paper, we present a more unified and simplified proof that brings both of these results together. By leveraging the recent findings of Bryant, Horsley, and Pettersson, we can bypass the need for the more complex difference methods and pull-up techniques, instead relying on the underlying principles elucidated in their work. This approach not only simplifies the proof process but also provides a clearer and more direct route to understanding the structure of neighborhood graphs in these maximum packings.