On biregular bipartite graphs of small excess

Let m > n >= 2 and g >= 4 be positive integers. A graph G is called a bipartite (m, n; g) graph if it is a biregular bipartite graph of even girth g with the additional property that all vertices in each of the two partition sets are of the same degree; m in one of them, and n in the other. In analogy with the well-known Cage Problem, if we let v(G) denote the order of G, and let B(m, n; g) denote the natural lower bound for the order of bipartite (m, n; g)-graphs obtained as a generalization of the Moore bound for regular graphs, we call the difference v(G) - B(m, n; g) the excess of G. The focus of this paper is on the study of the question of the existence of bipartite (m, n; g)-graphs for given parameters (m, n; g) and excess at most 4. We prove that such graphs are rare by finding restrictive necessary arithmetic conditions on the parameters m, n and g. Furthermore, we prove the non-existence of bipartite (m, n; g)-graphs of excess at most 4 for all parameters m, n,g where g >= 10 and is not divisible by 4, and m > n >= 3. In the case when the girth of G is 6, we employ spectral analysis of the distance matrices of G, and find necessary relations between their eigenvalues. Finally, we prove for all pairs m, n, m > n >= 3, that the asymptotic density of the set of even girths g >= 8 for which there exists a bipartite (m, n; g)-graph with excess not exceeding 4 is equal to 0. (C) 2019 Elsevier B.V. All rights reserved.