14
$\begingroup$

It is a wellknown fact, that Moebius Ladder Graphs have $2n$ vertices, but nowhere could I find any hint of how to generalize them to Graphs with $2n+1$ vertices.

Last week I had the idea of giving up the restriction to cubic graphs and arrived at glueing together the two ends of triangle strips with $2n+1$ triangles in the "Moebius manner", i.e. with a twist.

The result is

Moebius Stairway Graph

  • a $4$-regular graph
  • with exactly two edge-disjoint Hamiltonian cycles if $2n+1\ge 7$ , which contrasts the situation of Moebius Ladders, where the number of Hamiltonian cycles is different for each size and given by A124356 - OEIS and none contains a pair of edge-disjoint Hamiltionian cycles.
  • the chromatic number is $5$ for $5$ vertices and $4$ for all other cases of $2k+1$ vertices, again contrasting the situation of Moebius Ladders, where it is $2$ for $4k+2$ vertices and $3$ for $4k$ vertices (for 4 vertices it would also be $4$, but $K_4$ is normally not considered to be a Moebius Ladder)

Question:

Have those Moebius Stairway graphs been described or studied already, i.e. are further special properties known?

As a remark let me explain the name "Moebius Stairway" graph: if the triangles are chosen to be isosceles right triangles and the strip is then drawn in an ascending $45^{\circ}$ angle, it looks somewhat similar to a stairway and, besides that, I liked the idea of providing an alternative to ladders.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Is it the same as the "Mobius lattice" discussed in Kocay & Kreher, Graphs, Algorithms, and Optimization? $\endgroup$
    – Gerry Myerson
    Commented Jan 28, 2017 at 22:29
  • $\begingroup$ (Of course you can't have a cubic graph with $2n+1$ vertices, because the degree sum of any graph has to be an even number.) $\endgroup$
    – Pat Devlin
    Commented Feb 17, 2017 at 4:21

4 Answers 4

Reset to default
15
$\begingroup$

They are called quartic Möbius ladders.

They are one of the fundamental classes in Johnson & Thomas's classification of internally 4-connected graphs, and crop up in matroid theory for the same reason.

http://dx.doi.org/10.1006/jctb.2001.2089

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for answering my question; I guess I would never have found the connection between odd number of vertices and quartic Moebius "ladders". $\endgroup$
    – Manfred Weis
    Commented Jan 29, 2017 at 8:09
8
$\begingroup$

I don't know if this family has a special name, but it is a simple type of circulant graph. Consider this way to draw it (for 9 vertices).

enter image description here

I don't know why you say it has only two hamiltonian cycles as it has many (82 in fact). Here's one beyond the two obvious ones: 0,1,5,4,3,2,6,7,8.

For $n=5,7,9,\ldots,37$, the number of hamiltonian cycles is 24,46,82,158,316,650,1364,2892,6170,13206,28314,60760,130446,280120, 601600,1292102,2775226,5960822.

Not in OEIS. Can you fit a formula or recurrence to it?

[Added] David Zhang has found an empirical recurrence for the numbers, which I'm sure is correct. Also, he is correct that I counted each cycle once in each direction -- I used a program designed for digraphs. I'll divide by 2 from now on. We can solve the recurrence with Maple's help. Let $\omega_1,\omega_2,\omega_3$ be the zeros of $x^3+2x^2+x-1$. Then the number of cycles for $n=2k+1$ (if the recurrence is correct) is $$ 2 + 2k + \sum_{j=1}^3 \frac{1}{(\omega_j+1) \omega_j^{k+1}}.$$ Approximate values are: $\omega_1=0.4655712319$, $\omega_2,\omega_3 = 1.232785616\pm 0.7925519925i$. Obviously the terms with $\omega_2$ and $\omega_3$ quickly become negligible. From $n=7$ onwards, the number of cycles is the nearest integer to $$ 2 + 2k+ \frac{1}{(\omega_1+1) \omega_1^{k+1}}.$$

Improve this answer
$\endgroup$
8
  • $\begingroup$ Nice answer, especially pointing out my misconception about the number of Hamiltonian cycles and the interesting sequence of their number. The basic property of the circulant graphs was already known to me; the "diagonals" connect vertices whose "label distance" (modulo $n/2$ is relatively prime to $n$ and $<n/2$ $\endgroup$
    – Manfred Weis
    Commented Jan 29, 2017 at 7:44
  • $\begingroup$ Brendan, do you have further information about counting/generating Hamiltonian cycles in quartic Möbius ladders? Where do the numbers in your answer come from, i.e. who calculated them and why. If you could provide me with pointers to (online) resources, that would be great. $\endgroup$
    – Manfred Weis
    Commented Feb 16, 2017 at 10:39
  • $\begingroup$ @ManfredWeis I counted the cycles myself by brute force. I don't know anything else about it. $\endgroup$
    – Brendan McKay
    Commented Feb 16, 2017 at 12:08
  • $\begingroup$ Thanks for the immediate reply; I am currently trying to identify some "building blocks" of those Hamiltionian cycles. I found some, but can't yet see any rules how to assemble them. My hope is something like a set of replacement rules that generate longer cycles from smaller ones by replacing single nodes or edges with one of the building blocks. $\endgroup$
    – Manfred Weis
    Commented Feb 16, 2017 at 12:55
  • 1
    $\begingroup$ These numbers appear to satisfy the third-order linear recurrence $$a_{n+3} = a_n + 2a_{n+1} + a_{n+2} - 16 - 12n \qquad a_2 = 24 \qquad a_3 = 46 \qquad a_4 = 82$$ where $a_n$ denotes the number of Hamiltonian cycles in the Möbius stairway with $2n+1$ vertices. (Btw, it looks like you're counting each cycle and its reverse as distinct. Mathematica finds numbers exactly one-half of yours.) $\endgroup$
    – David Zhang
    Commented Feb 17, 2017 at 11:28
5
$\begingroup$

I think Gerry's right; this is the construction that Kocay & Kreher in Graphs, Algorithms, and Optimization call the Möbius lattice (definition 13.18 on p. 365 of the 2004 edition, definition 15.21 on p. 403 of the 2016 edition, just after Möbius ladder). Their projective embedding of $L_7$ below corresponds to your graph (with appropriate vertex labels).

enter image description here

(The dotted line and $D_i$ are about changing this to a toroidal embedding.)

It doesn't seem like their name for this family of graphs is widely used; I found one undergraduate thesis mention it in an aside and some possibly relevant physics research.

As to further study, Möbius lattices come up in two exercises of Kocay & Kreher:

(1) Show that the Möbius ladder $L_{2n-2}$ is a minor of the Möbius lattice $L_{2n+1}$ for $n \ge 3$.

(2) Show that the Möbius lattice $L_{2n-1}$ has an embedding on the torus in which all faces are quadrilaterals.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice background information and illustrative drawing. $\endgroup$
    – Manfred Weis
    Commented Jan 29, 2017 at 8:10
2
$\begingroup$

This is the square of an odd cycle. If you found it as a spanning subgraph of another graph you might call it the square of a Hamilton cycle. There are lots of results about powers of cycles from this opposite perspective; for example, they appear at minimum degree $2n/3$ or in random graphs at $p = 1/\sqrt n$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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