Small Locally \(nK_2\) Graphs

F. Larrion1, M.A. Pizana2, R. Villarroel-Flores3
1 Instituto de MatemAticas. Universidad Nacional Aut6noma de México. México, D.F. C.P. 04510.
2Depto. de Ingenieria Eléctrica. Universidad Auténoma Metropolitana, Av. San Rafael Atlixco 186, Col Vicentina, México 09340 D.F. MEXICO.
3Centro de Investigaci6n en Matematicas, Universidad Auténoma del Estado de Hidalgo, Carr. Pachuca-Tulancingo km. 4.5, Pachuca Hgo. 42184, MEXICO.

Abstract

A locally \(nK_2\) graph \(G\) is a graph such that the set of neighbors of any vertex of \(G\) induces a subgraph isomorphic to \(nK_2\). We show that a locally \(nK_2\) graph \(G\) must have at least \(6n – 3\) vertices, and that a locally \(nK_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.