8
$\begingroup$

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.

A January 2024 update: there are none with less than 64 vertices. Related to this is the question of how many edges a bipartite graph can have without 8-cycles. For $n\le 63$, the maximum is achieved uniquely by $K_{3,n-3}$, whose average degree is $6-\frac{18}n$. So a 6-regular example would break this pattern.

Improve this question
$\endgroup$
8
  • $\begingroup$ Have you tried things like Cayley graphs or poset Hasse diagrams for well-structured posets? $\endgroup$
    – Patricia Hersh
    Commented Jul 29, 2012 at 14:40
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 29, 2012 at 16:03
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerry Myerson
    Commented Jul 29, 2012 at 23:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Jul 30, 2012 at 3:07
  • 1
    $\begingroup$ 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." $\endgroup$
    – joro
    Commented Aug 2, 2012 at 7:11

1 Answer 1

Reset to default
2
$\begingroup$

Hi Brendan. I just happened upon this while searching for some related material, and I'm not sure if you're still interested in finding such a graph. I'm relatively certain I can construct one on 7812 vertices, following a few old ideas used by Lazebnik, Ustimenko and me in a series of papers on extremal graphs (in the sense of Turan). In fact the 7812-vertex graph I mention has girth 10, and its construction, as well as a proof that the girth is 10, should be easy to follow, and/or present. Let me know if you're still interested. I'll be looking back here every so often. Or just drop me an email. Regards.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi Andrew, There is a generalized hexagon on 7812 vertices mentioned in one of my comments above. But I'm still hopeful that a very much smaller graph (maybe even less than 100 vertices) is possible if 4-cycles and 6-cycles are allowed. $\endgroup$
    – Brendan McKay
    Commented Mar 16, 2013 at 5:59
  • $\begingroup$ Brendan, you're correct. This is the same graph, only my model is constructed in a way that can be readily explained to, for example, a grad student who is not well versed in rank 2 groups of Lie type or generalized n-gons. I'm going to think more on this problem. I find it very intriguibg. One can reduce 7812 for sure, for example by constructing the polarity graph of the generalized hexagon, which introduces smaller cycles, but this merely cuts the verex set in half ... not the kind of numbers you're looking for. Cheers. $\endgroup$
    – Andrew Woldar
    Commented Mar 16, 2013 at 15:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .