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.
Small regular graphs of girth 7
ABREU, Marien;LABBATE, Domenico;
2015-01-01
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≥4, and of order 2q^3+2q^2−q+1 for each odd prime power q≥5.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
