Small Regular Graphs of Girth 7

  • M. Abreu
  • G. Araujo-Pardo
  • C. Balbuena
  • D. Labbate
  • J. Salas
Keywords: Cages, girth, incidence graph

Abstract

In this paper, we construct new infinite families of regular graphs of girth 7 of smallest order known so far. Our constructions are based on combinatorial and geometric properties of $(q+1,8)$-cages, for $q$ a prime power. We remove vertices from such cages and add matchings among the vertices of minimum degree to achieve regularity in the new graphs. We obtain $(q+1)$-regular graphs of girth 7 and order $2q^3+q^2+2q$ for each even prime power $q \ge 4$, and of order $2q^3+2q^2-q+1$ for each odd prime power $q\ge 5$.

 

A corrigendum was added to this paper on 21 June 2016.

Published
2015-07-01
Article Number
P3.5