Search

Let $q$ be a prime power and $r=0,1\ldots, q-3$. Using the Latin squares obtained by multiplying each entry of the addition table of the Galois field of order $q$ by an element distinct from zero, we obtain the incidence matrices of projective planes and the incidence matrices of $(q-r)$-regular bipartite graphs of girth 6 and $q^2-rq-1$ vertices in each partite set. Moreover, in this work two Latin squares of order $q-1$ with entries belonging to $\{0,1,\ldots, q\}$, not necessarily the same, are defined to be quasi row-disjoint if and only if the Cartesian product of any two rows contains at most one pair $(x,x)$ with $x\ne 0$. Using these quasi row-disjoint Latin squares we find $(q-1)$-regular bipartite graphs of girth 6 with $q^2-q-2$ vertices in each partite set. Some of these graphs have the smallest number of vertices known so far among the regular graphs with girth 6.

In this article, some structures in the projective plane of order $q$ **image** are found which allow us to construct small $k$ **image** -regular balanced bipartite graphs of girth 6 for all $k\le q$ **image** . When $k=q$ **image** , the order of these $q$ **image** -regular graphs is $2(q^2-1)$ **image** ; and when $k\le q-1$ **image** , the order of these $k$ **image** -regular graphs is $2(qk-2)$ **image** . Moreover, the incidence matrix of a $k$ **image** -regular balanced bipartite graph of girth 6 having $2(qk-2)$ **image** vertices, where $k$ **image** is an integer and $q$ **image** is a prime power with $3\le k\le q-1$ **image** , 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 © 2011 Wiley Periodicals, Inc.