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 $k$ ‐regular balanced bipartite graphs of girth 6 for all $k\le q$ . When $k=q$ , the order of these $q$ ‐regular graphs is $2(q^2-1)$ ; and when $k\le 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\le k\le q-1$ , is provided. These graphs improve upon the best known upper bounds for the number of vertices in regular graphs of girth 6. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 121–127 2011