Universitat Politècnica de Catalunya
Universitat Politècnica de Catalunya. Departament d'Enginyeria Civil i Ambiental
Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
2017-08
© 2017. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
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 results.
Peer Reviewed
Postprint (author's final draft)
Article
Anglès
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria; Graph theory; Small regular graphs; Cage; Girth; Amalgam; Grafs, Teoria de; Classificació AMS::05 Combinatorics::05C Graph theory
http://www.sciencedirect.com/science/article/pii/S0012365X17301000
Open Access
E-prints [72986]
