Biregular cages of girth five

Original · EN

Let 2 ≤ r < m and g be positive integers. An (r,m;g)--graph (or biregular graph) is a graph with degree set r,m and girth g, and an (r,m;g)-cage (or biregular cage) is an (r,m;g)-graph of minimum order n(r,m;g). If m=r+1, an (r,m;g)-cage is said to be a semiregular cage. In this paper we generalize the reduction and graph amalgam operations from M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate (2011) on the incidence graphs of an affine and a biaffine plane obtaining two new infinite families of biregular cages and two new semiregular cages. The constructed new families are (r,2r-3;5)-cages for all r=q+1 with q a prime power, and (r,2r-5;5)-cages for all r=q+1 with q a prime. The new semiregular cages are constructed for r=5 and 6 with 31 and 43 vertices respectively.