Generating graphs of girth $g$ such that the minimum cycles form a double edge cover

Question

Let $g\geq 3$. I need to generate simple graphs $G$ of girth $g$ such that the set of all $g$-cycles forms a double edge cover of $G$ (that is, every edge is shared by exactly two $g$-cycles), and such that the intersection of any two $g$-cycles is either a vertex, an edge, or empty. The generated graphs should be arbitrarily large.

The method of generation should have some randomness to it, but not in a trivial sense. I want to be able to obtain fairly complicated graphs. For example, imagine an $n\times m$ rectangular grid in the plane. If we identify the opposite sides of the bounding rectangle, we obtain a graph that satisfies all of the above requirements for $g=4$. I would qualify this graph as simple.

Is there any such method?

Any references to similar problems are also appreciated.

Answer 1

My half-baked idea was a little too ambitious. I'm including it below for reference, but the distance condition I specified is not actually sufficient to guarantee large girth.

There are arbitrarily large highly symmetric surface maps with large girth, but published existence proofs are largely based on group theory rather than topology or geometry per se.

Specifically, for any integers $g$, $d$, and $r$ such that $1/g + 1/d < 1/2$, there is a regular surface map in which every face has $g$ edges, every vertex has degree $d$, and every non-contractible cycle on the surface crosses at least $r$ edges. Here "regular" means both that every vertex has the same degree and that for any pair of directed edges, there is an automorphism of the embedding that sends directed edge to the other. Setting $r$ large enough in this construction guarantees that the girth of the graph is $g$. See, for example:

• Roman Nedela and Martin Škoviera. Regular maps on surfaces with large planar width. European J. Combinatorics 22(2):243--262, 2001.

• Jozef Širáň. Triangle group representations and constructions of regular maps. Proc. London Math. Soc. 82(3):513-532, 2001.

Once you have one such surface map, larger maps with the same girth and degree can be generated by constructing covering spaces.

---

Here is one (half-baked) way to generate such graphs. Let $G$ be a plane graph with the following properties:

• Every bounded face of $G$ has exactly $g$ edges.

• The outer face of $G$ has an even number of edges; call these the boundary edges of $G$. (This condition holds automatically when $g$ is even; if $g$ is odd, $G$ must have an even number of bounded faces.)

• It is possible to pair the boundary edges of $G$, so that the distance in $G$ from any boundary edge to its partner is at least $g$. This condition is not actually enough; the exact condition needed here is unclear.

Arbitrarily large plane graphs with these properties can be constructed by taking a sufficiently large finite portion of a regular tiling of the hyperbolic plane by $g$-gons.

Finally, to obtain a surface graph $G'$ where every face has length $g$, identify pairs of boundary edges in $G$ according to the pairing described above. The bounded faces of $G$ become the faces of a cellular embedding of $G'$ on some closed surface without boundary. The distance condition on the pairing guarantees that the girth of $G'$ is $g$.

By choosing both $G$ and the pairing more carefully, once can construct arbitrarily large $d$-regular graphs satisfying your girth condition, for any integers $d$ and $g$ such that $1/d + 1/g < 1/2$. Even within these constraints, the construction has lots of degrees of freedom.