Loading...
Loading...

Go to the content (press return)

New small regular graphs of girth 5

Author
Abajo, E.; Araujo-Pardo, G.; Balbuena, C.; Bendala, M.
Type of activity
Journal article
Journal
Discrete mathematics
Date of publication
2017-08
Volume
340
Number
8
First page
1878
Last page
1888
DOI
https://doi.org/10.1016/j.disc.2017.03.020 Open in new window
URL
http://www.sciencedirect.com/science/article/pii/S0012365X17301000 Open in new window
Abstract
A (k,g)-graph is a k-regular graph with girth g and a (k,g)-cage is a (k,g)-graph with the fewest possible number of vertices. The cage problem consists of constructing (k,g)-graphs of minimum order n(k,g). We focus on girth g=5, where cages are known only for degrees k=7. We construct (k,5)-graphs using techniques exposed by Funk (2009) and Abreu et al. (2012) to obtain the best upper bounds on n(k,5) known hitherto. The tables given in the introduction show the improvements obtained with our...
Keywords
Amalgam, Cage, Girth, Small regular graphs
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants