Small Locally $n{K}_2$ Graphs

Abstract

A locally $n{K}_2$ graph $G$ is a graph such that the set of neighbors of any vertex of $G$ induces a subgraph isomorphic to $n{K}_2$. We show that a locally $n{K}_2$ graph $G$ must have at least $6n–3$ vertices, and that a locally $n{K}_2$ graph with $6n–3$ vertices exists if and only if $n\in \{1,2,3,5\}$, and in these cases the graph is unique up to isomorphism. The case $n=5$ is surprisingly connected to a classic theorem of algebraic geometry: The only locally $5K_2$ graph on $6\times 5–3=27$ vertices is the incidence graph of the 27 straight lines on any nonsingular complex projective cubic surface.