Geodesic
Small regular graphs of girth 7
M. Abreu1 ; G. Araujo-Pardo2 ; C. Balbuena3 ; D. Labbate1 ; J. Salas4
1Dipartimento di Matematica, Informatica ed Economia Università degli Studi della Basilicata Viale dell'Ateneo Lucano,10 I-85100 Potenza, Italy.
2Instituto de Matemáticas Campus Juriquilla Universidad Nacional Autónoma de México Juriquilla 76230 Querétaro, México.
3Departament de Matemática Aplicada III Universitat Politècnica de Catalunya Campus Nord, Edifici C2 C/ Jordi Girona 1-3 E-08034 Barcelona, Spain. and Matemáticas Aplicadas y Sistemas Universidad Autónoma Metropolitana unidad de Cuajimalpa Av. Vasco de Quiroga 4871, Col. Santa Fé, Cuajimalpa, México, D.F. 05348, México.
4Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Paisos Catalans, 26 43007 Tarragona, Spain.
The electronic journal of combinatorics, Tome 22 (2015) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/4205
Classification : 05C35, 51E12
Mots-clés : cages, girth, incidence graph

M. Abreu  1   ; G. Araujo-Pardo  2   ; C. Balbuena  3   ; D. Labbate  1   ; J. Salas  4

1 Dipartimento di Matematica, Informatica ed Economia Università degli Studi della Basilicata Viale dell'Ateneo Lucano,10 I-85100 Potenza, Italy.
2 Instituto de Matemáticas Campus Juriquilla Universidad Nacional Autónoma de México Juriquilla 76230 Querétaro, México.
3 Departament de Matemática Aplicada III Universitat Politècnica de Catalunya Campus Nord, Edifici C2 C/ Jordi Girona 1-3 E-08034 Barcelona, Spain. and Matemáticas Aplicadas y Sistemas Universidad Autónoma Metropolitana unidad de Cuajimalpa Av. Vasco de Quiroga 4871, Col. Santa Fé, Cuajimalpa, México, D.F. 05348, México.
4 Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Paisos Catalans, 26 43007 Tarragona, Spain. 
@article{10_37236_4205,
     author = {M. Abreu and G. Araujo-Pardo and C. Balbuena and D. Labbate and J. Salas},
     title = {Small regular graphs of girth 7},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {3},
     doi = {10.37236/4205},
     zbl = {1327.05163},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4205/}
}
TY  - JOUR
AU  - M. Abreu
AU  - G. Araujo-Pardo
AU  - C. Balbuena
AU  - D. Labbate
AU  - J. Salas
TI  - Small regular graphs of girth 7
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4205/
DO  - 10.37236/4205
ID  - 10_37236_4205
ER  - 
%0 Journal Article
%A M. Abreu
%A G. Araujo-Pardo
%A C. Balbuena
%A D. Labbate
%A J. Salas
%T Small regular graphs of girth 7
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4205/
%R 10.37236/4205
%F 10_37236_4205
M. Abreu; G. Araujo-Pardo; C. Balbuena; D. Labbate; J. Salas. Small regular graphs of girth 7. The electronic journal of combinatorics, Tome 22 (2015) no. 3. doi: 10.37236/4205

Cité par Sources :