# 6-regular bipartite graphs with no 8-cycles

I'm looking for simple 6-regular bipartite graphs with no 8-cycles, as small as possible. It doesn't matter if there are 4-cycles or 6-cycles, provided there are no 8-cycles. Such graphs must exist since the girth can be arbitrarily high, but what smaller examples are there? There are certainly none on less than 46 vertices.

• Have you tried things like Cayley graphs or poset Hasse diagrams for well-structured posets? – Patricia Hersh Jul 29 '12 at 14:40
• More specifically, can you take a dimension 7 hypercube graph and remove some edges from it? Gerhard "Ask Me About System Design" Paseman, 2012.07.29 – Gerhard Paseman Jul 29 '12 at 16:03
• I'm sure Brendan knows about these resources, but there's a table of cages (regular graphs with high girth and few vertices) at mapleta.maths.uwa.edu.au/~gordon/remote/cages/allcages.html, and a paper on small regular bipartite graphs of girth 8 (with a bibliography listing many papers on related topics) at ma3.upc.edu/users/balbuena/PAPERS/consgirth8.pdf – Gerry Myerson Jul 29 '12 at 23:07
• Some quotients of tilings of the hyperbolic plane would work, but I don't know how large they would have to be. Cycles are either contractible or not. If the tiling is of decagons or hexagons, or alternating squares and decagons, then there are no contractible octogons. – Douglas Zare Jul 30 '12 at 3:07
• The program "girth" from the Stanford GraphBase found a large Ramanujan graph with p,q=5,37: "So the diameter is 10, and the girth is 10. The graph has 50616 vertices, each of degree 6, and it is bipartite." – joro Aug 2 '12 at 7:11