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 >= 4, and of order 2q(3) + 2q(2) q + 1 for eac...
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 >= 4, and of order 2q(3) + 2q(2) q + 1 for each odd prime power q >= 5.
Citation
Abreu, M., Araujo-Pardo, G., Balbuena, C., Labbate, D., Salas, J. Small regular graphs of girth 7. "Electronic journal of combinatorics", 01 Juliol 2015, vol. 22, núm. 3, p. 1-16.