Abstract:

The size of the smallest k-regular graph of girth g is denoted by the well studied function n(k,g). We suggest generalizing this function to n(H,g), defined as the smallest size girth g graph covering the, possibly non-regular, graph H. We prove that the two main combinatorial bounds on n(k,g), the Moore Lower bound and the Erdos--Sachs upper bound, carry over to the new setting of lifts, even in their non-asymptotic form.
We also explore two other generalizations of n(k,g). Namely, the minimal size girth g graph sharing a universal cover with H, and the minimal size girth g graph with the same degree distribution as H. We show that the former is the same as n(H,g) up to a multiplicative constant, but the latter may or may not be separated by an exponential gap, depending on the base graph H. We conclude with experimental results for a specific base graph and a conjecture.