Semicubic cages and small graphs of even girth from voltage graphs

arXiv2305.03290MaRDI QIDQ6435441FDOQ6435441

Flor Aguilar, Leah Bermann, G. Araujo-Pardo

Publication date: 5 May 2023

Abstract: An emph{$(3,m;g)$ semicubic graph} is a graph in which all vertices have degrees either $3$ or $m$ and fixed girth $g$. In this paper, we construct families of semicubic graphs of even girth and small order using two different techniques. The first technique generalizes a previous construction which glues cubic cages of girth $g$ together at remote vertices (vertices at distance at least $g/2$). The second technique, the main content of this paper, produces bipartite semicubic $(3,m;g)$-graphs with fixed even girth $g=4t$ or $4t+2$ using voltage graphs over $mathbb{Z}_m$. When $g=4t+2$, the graphs have two vertices of degree $m$, while when $g=4t$ they have exactly three vertices of degree $m$ (the remaining vertices are of degree $3$ in both cases). Specifically, we describe infinite families of semicubic graphs $(3,m;g)$ for $g=6,8,10,12$ for infinitely many values of $m$. The cases $g=6,8$ include the unique $6$-cage and the unique $8$-cage when $m=3$. The families obtained in this paper for girth $g=10,12$ include examples with the best known bounds for semicubic graphs $(3,m;g)$

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

This page was built for publication: Semicubic cages and small graphs of even girth from voltage graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435441)