Semicubic cages and small graphs of even girth from voltage graphs

english

2026

volume 26, issue 3, article p3.03

girth   graph   semicubic graph   voltage graph

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

A ({3, m}; g)-semicubic graph is a graph where the degree of each vertex is either 3 or m and the girth of the graph is g; if m = 3 we have a cubic graph. 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 of even girth g using voltage graphs over Zm. For girth g = 4t + 2, t ? 1, the constructed graphs have two vertices of degree m. For girth g = 4t, t ? 2, the construction produces graphs with exactly three vertices of degree m (of course, the remaining vertices are of degree 3 in both cases). In particular, we describe infinite families of ({3, m}; g)-semicubic graphs 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 of orders that match the best-known bounds for ({3, m}; g)-semicubic graphs until this moment.

27.10.2026