Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

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.

share|improve this answer
    
If the parallelogram is a rhombus you get a symmetric graph, not just a vertex-transitive graph. If the rhombus has sides parallel to the tiling then the smallest you get is $F_{54}$, the 54-vertex symmetric graph in the Foster census, but with a tilted rhombus $F_{42}$ is possible. This construction of both of these graphs are shown in my paper arXiv:0709.4087. –  David Eppstein Mar 10 '10 at 20:00
add comment

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;

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.