On biregular bipartite graphs of small excess (Q2421873): Difference between revisions

Let \(m>n>2\) and \(g\geq 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 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. 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. By the motivation of the well-known cage problem, the authors investigate the difference \(v(G)-B(m, n; g)\), called the excess of \(G\), where \(v(G)\) is the order of \(G\). Mainly, it is shown that such bipartite graphs of excess at most 4 with parameters \((m, n; g)\) are rare.