Looking for cubic, bipartite graphs with girth at least six and no cycles of length 8.

Question

Aside from the Desargues graph, are there nice (at least vertex-transitive), small (say, less than 60 vertices), cubic, bipartite graphs with girth at least 6 and no 8-cycles? (or, even better, no cycles of length congruent to 0 mod 4.)

Bonus: any idea how to use Mathematica to pull these out of its list of graphs it's got data for in Mathematica 7?

Answer 1

Sure, form a torus graph by cutting a big parallelogram out of the tiling of the plane by regular hexagons and gluing opposite sides together. Any short cycle has length 6 (one hex) or length ≥ 10 (two or more hexes), and by making the parallelogram big enough you can also force the noncontractible cycles to be as long as you want.

As for avoiding cycles with lengths that are multiples of four: that would be in contradiction to the Erdős–Gyárfás conjecture which states that every graph with minimum degree at least three has a simple cycle of length a power of two.

Answer 2

The Desargues graph does have cycles of length 8 though, doesn't it?

But here's a nice 38-vertex bipartite cubic vertex-transitive graph with no 4 or 8 cycles:

Graph 1, order 38. 0 : 1 2 3; 1 : 0 4 7; 2 : 0 6 9; 3 : 0 5 8; 4 : 1 10 13; 5 : 3 11 15; 6 : 2 12 14; 7 : 1 11 16; 8 : 3 12 18; 9 : 2 10 17; 10 : 4 9 28; 11 : 5 7 26; 12 : 6 8 27; 13 : 4 32 35; 14 : 6 34 37; 15 : 5 33 36; 16 : 7 29 35; 17 : 9 31 37; 18 : 8 30 36; 19 : 29 30 31; 20 : 27 32 34; 21 : 28 32 33; 22 : 26 33 34; 23 : 27 30 35; 24 : 28 31 36; 25 : 26 29 37; 26 : 11 22 25; 27 : 12 20 23; 28 : 10 21 24; 29 : 16 19 25; 30 : 18 19 23; 31 : 17 19 24; 32 : 13 20 21; 33 : 15 21 22; 34 : 14 20 22; 35 : 13 16 23; 36 : 15 18 24; 37 : 14 17 25;

Answer 3

Desargues graph, also known as the generalized Petersen graph $G(10,3)$ has girth 6 and also contains cycles of length 8. There exist three 10-cages, smallest cubic graphs of girth 10. They have 70 vertices and none of them is vertex-transitive. For more information about the motivation see here.

Therefore it is quite surprising that Gordon's example is so small. By the way, it is also arc-transitive. One may consider it as a Levi graph of a self-dual, flag-transitive 3-configuration of 19 points and 19 lines. Configuration contains triangles but has no quadrangles.

Here is a geometric realization of this graph.

Configuration with triangles but no quadrangles

1. A natural question is, whether this is the smallest graph with required properties.

2. Another related question is, whether there exist smaller bipartite graphs if the vertex-transitivity condition is dropped.