Constructions of Small Regular Bipartite Graphs of Girth 6

摘要

In this article, some structures in the projective plane of order q are found which allow us to construct small Irregular balanced bipartite graphs of girth 6 for all k < q. When k = q, the order of these q-regular graphs is 2(q~2-1); and when k ≤ q-1, the order of these k-regular graphs is 2(qk - 2). Moreover, the incidence matrix of a k-regular balanced bipartite graph of girth 6 having 2(qk - 2) vertices, where k is an integer and q is a prime power with 3≤k≤q-1, is provided. These graphs improve upon the best known upper bounds for the number of vertices in regular graphs of girth 6.