Möbius Ladder
المؤلف:
Biggs, N. L
المصدر:
Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press
الجزء والصفحة:
...
22-3-2022
2496
Möbius Ladder
A Möbius ladder, sometimes called a Möbius wheel (Jakobson and Rivin 1999), of order 
is a simple graph obtained by introducing a twist in a prism graph of order 
that is isomorphic to the circulant graph 
. Möbius ladders are sometimes denoted 
.
The 4-Möbius ladder is known as the Wagner graph. The 
-Möbius ladder rung graph is isomorphic to the Haar graph 
.
Möbius ladders are Hamiltonian, graceful (Gallian 1987, Gallian 2018), and by construction, singlecross. The Möbius ladders are also nontrivial biplanar graphs.
The numbers of directed Hamiltonian cycles for 
, 4, ... are 12, 10, 16, 14, 20, 18, 24, ... (OEIS A124356), given by the closed form
![|HC(n)|=2[(n+2)-(-1)^n].](https://mathworld.wolfram.com/images/equations/MoebiusLadder/NumberedEquation1.svg) |
(1)
|
The 
-Möbius ladder graph has independence polynomial
![I_n(x)=2^(-n)[-2^n(-x)^n+(x-sqrt(x(x+6)+1)+1)^n+(x+sqrt(x(x+6)+1)+1)^n].](https://mathworld.wolfram.com/images/equations/MoebiusLadder/NumberedEquation2.svg) |
(2)
|
Recurrence equations for the independence polynomial and matching polynomial are given by
The bipartite double graph of the 
-Möbius ladder is the prism graph 
.
REFERENCES
Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 20-21, 1993.
Gallian, J. "Labeling Prisms and Prism Related Graphs." Congr. Numer. 59, 89-100, 1987.
Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018.
https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 118 and 131, 2001.
Hladnik, M.; Marušič, D.; and Pisanski, T. "Cyclic Haar Graphs." Disc. Math. 244, 137-153, 2002.
McSorley, J. P. "Counting Structures in the Moebius Ladder." Disc. Math. 184, 137-164, 1998.
Jakobson, D. and Rivin, I. "On Some Extremal Problems in Graph Theory." 8 Jul 1999.
http://arxiv.org/abs/math.CO/9907050.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 270, 1998.
Sloane, N. J. A. Sequence A124356 in "The On-Line Encyclopedia of Integer Sequences."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
