Discrete Mathematics & Theoretical Computer Science, Vol 11, No 2 (2009)

Font Size:  Small  Medium  Large

A method for obtaining small regular bipartite graphs of girth 8

Camino Balbuena


Let q be a prime a power and k an integer such that 3 ≤ k ≤ q. In this paper we present a method using Latin squares to construct adjacency matrices of k-regular bipartite graphs of girth 8 on 2(kq2-q) vertices. Some of these graphs have the smallest number of vertices among the known regular graphs with girth 8.

Full Text: PDF PostScript