Premium
Constructions of small regular bipartite graphs of girth 6
Author(s) -
AraujoPardo G.,
Balbuena Camino
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20392
Subject(s) - combinatorics , mathematics , bipartite graph , girth (graph theory) , odd graph , discrete mathematics , chordal graph , strongly regular graph , graph , pathwidth , 1 planar graph , line graph
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