3
$\begingroup$

I found two different definitions of the Moebius Ladder Graph, whose essential difference is, whether the smallest one shall be $K_4$ or $K_{3,3}$.

according to Wikipedia (http://en.wikipedia.org/wiki/M%C3%B6bius_ladder),
"In graph theory, the Möbius ladder Mn is a cubic circulant graph with an even number n of vertices, formed from an n-cycle by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle".
that definition would cover $K_4$ as a Moebius Ladder.

according to Wolfram's Mathworld (http://mathworld.wolfram.com/MoebiusLadder.html), however "A Möbius ladder, sometimes called a Möbius wheel (Jakobson and Rivin 1999), of order n is a simple graph obtained by introducing a twist in a prism graph of order n that is isomorphic to the circulant graph $Ci_{2n}(1,n)$." and, because an n-Prism graph has $2n$ vertices and $3n$ edges, that would imply, that the smallest Moebius Ladder graph is $K_{3,3}$ and not $K_4$.

The "dispute" reminds me somehow of the "is 1 a prime number" topic and I would therefore like to know, if there are mathematical reasons in favor or against either of the definitions (I would however not count the analogy to the one-sided Moebius surface as sufficient justification).

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ No, either definition is fine, just make sure to state what you mean when you use the terminology. $\endgroup$
    – Brendan McKay
    Mar 30, 2014 at 18:25
  • $\begingroup$ It just occured to me, that $K_4$ is exceptional regarding vertex coloring: disallowing $K_4$ makes Moebius Ladders with $4k$ vertices 3-colorable and Moebius Ladders with $4k+2$ vertices 2-colorable; $K_4$ requires however four colors and would need separate treatment in that respect. $\endgroup$
    – Manfred Weis
    Mar 30, 2014 at 19:18
  • $\begingroup$ @BrendanMcKay the reason for my question is exactly why or when I have to say which definition I mean; a statement about the chromatic number of Moebius Ladders would be such an example. $\endgroup$
    – Manfred Weis
    Mar 30, 2014 at 19:25
  • 5
    $\begingroup$ You have to say which definition you mean if it makes a difference to what you say about these graphs. Any time some of your readers might have the wrong idea, play safe and tell them. $\endgroup$
    – Brendan McKay
    Mar 30, 2014 at 20:26

2 Answers 2

Reset to default
6
$\begingroup$

As far as I can see, the intent of both definitions is to give a description of the Moebius ladder as the circulant on $2n$ vertices with connection set $\{\pm 1, n\}$ which clearly includes $K_4$.

The "verbose" definition, as a prism with a twist etc. just seems to be wrong, basically because the first half of the definition contradicts the second. In this case, I'll go with the formal mathematical definition rather than the verbal part.

My graph-theorist's opinion: Smallest Moebius ladder is unambiguously $K_4$.

My matroid-theorist's opinion: Smallest Moebius ladder is actually $3K_2$ the graph with a triple edge connecting two vertices (i.e. the circulant with connection set +1, -1 and 1)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I "stumbled" upon the Moebius Ladder graph, when trying to "reverse engineer" Hamiltion Cycle problem, which led me to sequence of graphs starting with $K_4$, $K_{3,3}$, and from then on to Moebius Ladders with $2^n+2$ vertices as the cubic graphs, that are hamiltionian and have extremal arithmetic properties. $\endgroup$
    – Manfred Weis
    Mar 31, 2014 at 10:44
1
$\begingroup$

The issues, that I could identify so far, which could be brought forward, to exclude either $K_4$ or even also $K_{3,3}$ are the following:

$K_4$ should not count as a Moebius Ladder graph, because

  • it is planar, but not other Moebius Ladder is

  • it is not triangle-free, but all other Moebius Ladders are

  • its chromatic number is $4$, but the chromatic number of all other Moebius Ladders is either $2$ or $3$

  • it is not possible to tell the rung-edges from the rail-edges

$K_{3,3}$ should not count as a Moebius Ladder graph, because

  • it is not possible to tell the rung-edges from the rail-edges

I hope my list is understood as an appetizer for either identifying further issues or, for finding an unambiguous definition of what a Moebius Ladder graph shall be.
In analogy to prime numbers, $K_4$ could be excluded, because it has not enough structure; $K_{3,3}$ could be accepted and play a role analogous to $2$ as the oddest prime number - but that is a mere suggestion for disussion.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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