29:
508:
415:. The edges from the cycle from which the ladder is formed can be distinguished from the rungs of the ladder, because each cycle edge belongs to a single 4-cycle, while each rung belongs to two such cycles. Therefore, there is no symmetry taking a cycle edge to a rung edge or vice versa.
572:
to be a nonplanar graph for which every nontrivial minor is planar; he shows that 3-connected almost-planar graphs are Möbius ladders or members of a small number of other families, and that other almost-planar graphs can be formed from these by a sequence of simple operations.
594:
first synthesized molecular structures in the form of a Möbius ladder, and since then this structure has been of interest in chemistry and chemical stereography, especially in view of the ladder-like form of DNA molecules. With this application in mind,
611:: it cannot be converted into its mirror image by a continuous deformation of space without passing one edge through another. On the other hand, Möbius ladders with an even number of rungs all do have embeddings into
447:, it is not bipartite. The endpoints of each rung are an even distance apart in the initial cycle, so adding each rung creates an odd cycle. In this case, because the graph is 3-regular but not bipartite, by
366:, meaning that it cannot be drawn without crossings in the plane but removing one vertex allows the remaining graph to be drawn without crossings. These graphs have
484:
have the most spanning trees among all cubic graphs with the same number of vertices. However, the 10-vertex cubic graph with the most spanning trees is the
1075:
1544:
1375:
Integer
Programming and Combinatorial Optimization: 8th International IPCO Conference, Utrecht, The Netherlands, June 13–15, 2001, Proceedings
638:
approaches to problems of set packing and linear ordering. Certain configurations within these problems can be used to define facets of the
823:
230:
1370:
607:. In particular, as she shows, every three-dimensional embedding of a Möbius ladder with an odd number of rungs is topologically
1202:
790:
1432:
Proceedings of the Twenty-Second
Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991)
1239:
1125:
367:
1414:
646:
901:
Deng, Wen-Ji; Xu, Ji-Huan; Liu, Ping (2002). "Period halving of persistent currents in mesoscopic Möbius ladders".
1272:
1036:
997:
864:
1549:
903:
390:
162:
1487:
Walba, D.; Richards, R.; Haltiwanger, R. C. (1982). "Total synthesis of the first molecular Möbius strip".
832:
955:
267:
190:
52:
43:
1337:
922:
522:
97:
992:
837:
635:
496:
65:
1475:
1353:
1327:
1311:"Persistent currents in a Möbius ladder: A test of interchain coherence of interacting electrons"
1297:
1197:
1161:
1100:
1061:
1022:
980:
938:
912:
889:
862:
Borndörfer, Ralf; Weismantel, Robert (2000). "Set packing relaxations of some integer programs".
821:
Bolotashvili, G.; Kovalev, M.; Girlich, E. (1999). "New facets of the linear ordering polytope".
643:
1377:. Lecture Notes in Computer Science. Vol. 2081. Berlin: Springer-Verlag. pp. 333–347.
448:
1517:
1318:
619:
1496:
1459:
1378:
1345:
1281:
1248:
1211:
1134:
1084:
1045:
1006:
964:
930:
873:
842:
799:
631:
492:
460:
452:
375:
114:
1471:
1439:
1422:
1390:
1310:
1293:
1262:
1225:
1188:
1148:
1096:
1057:
1018:
976:
885:
854:
813:
393:– they have symmetries taking any vertex to any other vertex – but (with the exceptions of
1467:
1435:
1418:
1386:
1366:
1289:
1258:
1221:
1184:
1144:
1092:
1053:
1034:
Grötschel, M.; Jünger, M.; Reinelt, G. (1985b). "Facets of the linear ordering polytope".
1014:
972:
881:
850:
809:
781:
580:
436:
412:
275:
202:
158:
134:
124:
622:
ring in experiments to study the effects of conductor topology on electron interactions.
318:
1341:
926:
1112:
485:
379:
322:
178:
1394:
1253:
28:
1538:
1479:
1026:
984:
942:
934:
893:
804:
785:
474:
288:
1357:
1301:
1270:
De Mier, Anna; Noy, Marc (2004). "On graphs determined by their Tutte polynomials".
1065:
1520:
1447:
1116:
1104:
950:
658:
596:
559:
526:
360:
326:
239:
1413:. Proceedings of Symposia in Applied Mathematics. Vol. 45. Providence, RI:
1234:
663:
271:
262:
206:
154:
507:
1285:
1157:
1088:
846:
541:
363:
166:
1382:
1349:
583:
minor can be derived by a sequence of simple operations from Möbius ladders.
1525:
1430:
Valdes, L. (1991). "Extremal properties of spanning trees in cubic graphs".
608:
444:
423:
317:
four-cycles which link together by their shared edges to form a topological
1216:
1139:
1120:
1411:
New scientific applications of geometry and topology (Baltimore, MD, 1992)
1332:
1073:
Gubser, Bradley S. (1996). "A characterization of almost-planar graphs".
917:
639:
603:) studies the mathematical symmetries of embeddings of Möbius ladders in
42:. For an animation showing the transformation between the two views, see
1500:
1166:
1463:
1049:
1010:
995:; Jünger, M.; Reinelt, G. (1985a). "On the acyclic subgraph polytope".
968:
877:
1371:"Fences are futile: on relaxations for the linear ordering problem"
649:
of the problem; these facets are called Möbius ladder constraints.
506:
371:
386:
explores embeddings of these graphs onto higher genus surfaces.
459:
show that the Möbius ladders are uniquely determined by their
266:
by adding edges (called "rungs") connecting opposite pairs of
1175:
Li, De-ming (2005). "Genus distributions of Möbius ladders".
1434:. Congressus Numerantium. Vol. 85. pp. 143–160.
1309:
Mila, Frédéric; Stafford, C. A.; Capponi, Sylvain (1998).
749:
544:
operations to combine planar graphs and the Möbius ladder
591:
761:
757:
521:
Möbius ladders play an important role in the theory of
1450:(1937). "Über eine Eigenschaft der ebenen Komplexe".
1160:(1999). "On some extremal problems in graph theory".
618:
Möbius ladders have also been used as the shape of a
753:
756:; Grötschel, Jünger, and Reinelt (
733:
525:. The earliest result of this type is a theorem of
216:
150:
133:
123:
113:
96:
64:
51:
21:
709:
495:of the Möbius ladders may be computed by a simple
1198:"A characterization of graphs with no cube minor"
321:. Möbius ladders were named and first studied by
579:shows that almost all graphs that do not have a
370:one, and can be embedded without crossings on a
1409:Simon, Jonathan (1992). "Knots and chemistry".
615:that can be deformed into their mirror images.
765:
693:
8:
1235:"Counting structures in the Möbius ladder"
750:Bolotashvili, Kovalev & Girlich (1999)
456:
278:, so-named because (with the exception of
27:
16:Cycle graph with all opposite nodes linked
1331:
1252:
1215:
1165:
1138:
916:
836:
803:
737:
330:
1489:Journal of the American Chemical Society
1076:Combinatorics, Probability and Computing
953:(1989). "Symmetries of Möbius ladders".
784:; Damerell, R. M.; Sands, D. A. (1972).
681:
592:Walba, Richards & Haltiwanger (1982)
674:
576:
697:
630:Möbius ladders have also been used in
600:
565:
530:
18:
721:
7:
824:SIAM Journal on Discrete Mathematics
734:Mila, Stafford & Capponi (1998)
754:Borndörfer & Weismantel (2000)
710:Biggs, Damerell & Sands (1972)
383:
14:
1177:Northeastern Mathematics Journal
488:, which is not a Möbius ladder.
1203:Journal of Combinatorial Theory
791:Journal of Combinatorial Theory
33:Two views of the Möbius ladder
1126:Canadian Mathematical Bulletin
786:"Recursive families of graphs"
231:Table of graphs and parameters
1:
1545:Parametric families of graphs
1415:American Mathematical Society
1254:10.1016/S0012-365X(97)00086-1
540:minor can be formed by using
378:. Thus, they are examples of
805:10.1016/0095-8956(72)90016-0
766:Newman & Vempala (2001)
694:Jakobson & Rivin (1999)
1566:
1233:McSorley, John P. (1998).
935:10.1088/0256-307X/19/7/333
626:Combinatorial optimization
1286:10.1007/s00373-003-0534-z
1089:10.1017/S0963548300002005
847:10.1137/S0895480196300145
738:Deng, Xu & Liu (2002)
229:
26:
1383:10.1007/3-540-45535-3_26
1350:10.1103/PhysRevB.57.1457
1273:Graphs and Combinatorics
1037:Mathematical Programming
998:Mathematical Programming
865:Mathematical Programming
457:De Mier & Noy (2004)
1121:"On the Möbius ladders"
904:Chinese Physics Letters
1217:10.1006/jctb.2000.1968
1196:Maharry, John (2000).
1140:10.4153/CMB-1967-046-4
533:) that graphs with no
518:
270:in the cycle. It is a
1452:Mathematische Annalen
956:Mathematische Annalen
587:Chemistry and physics
510:
1240:Discrete Mathematics
348:, the Möbius ladder
256:, is formed from an
1501:10.1021/ja00375a051
1417:. pp. 97–130.
1342:1998PhRvB..57.1457M
927:2002ChPhL..19..988D
636:integer programming
570:almost-planar graph
497:recurrence relation
389:Möbius ladders are
252:, for even numbers
1518:Weisstein, Eric W.
1464:10.1007/BF01594196
1156:Jakobson, Dmitry;
1050:10.1007/BF01582010
1011:10.1007/BF01582009
969:10.1007/BF01446435
878:10.1007/PL00011381
644:linear programming
551:; for this reason
519:
466:The Möbius ladder
1495:(11): 3219–3221.
1365:Newman, Alantha;
1319:Physical Review B
511:The Wagner graph
493:Tutte polynomials
461:Tutte polynomials
391:vertex-transitive
236:
235:
163:Vertex-transitive
1557:
1531:
1530:
1504:
1483:
1443:
1426:
1405:
1403:
1402:
1393:. Archived from
1367:Vempala, Santosh
1361:
1335:
1333:cond-mat/9705119
1326:(3): 1457–1460.
1315:
1305:
1266:
1256:
1247:(1–3): 137–164.
1229:
1219:
1192:
1171:
1169:
1152:
1142:
1108:
1069:
1030:
988:
946:
920:
918:cond-mat/0209421
897:
858:
840:
817:
807:
768:
747:
741:
731:
725:
719:
713:
707:
701:
691:
685:
679:
632:computer science
527:Klaus Wagner
453:chromatic number
410:
401:
376:projective plane
358:
347:
316:
309:
298:
286:
265:
260:
255:
251:
225:
211:
199:
187:
175:
145:
115:Chromatic number
108:
92:
91:
89:
88:
85:
82:
59:
41:
31:
19:
1565:
1564:
1560:
1559:
1558:
1556:
1555:
1554:
1535:
1534:
1521:"Möbius Ladder"
1516:
1515:
1512:
1507:
1486:
1446:
1429:
1408:
1400:
1398:
1364:
1313:
1308:
1269:
1232:
1195:
1174:
1167:math.CO/9907050
1155:
1113:Guy, Richard K.
1111:
1072:
1033:
991:
949:
900:
861:
820:
780:
776:
771:
748:
744:
732:
728:
720:
716:
708:
704:
692:
688:
682:McSorley (1998)
680:
676:
672:
655:
628:
620:superconducting
589:
557:
550:
539:
517:
505:
483:
472:
449:Brooks' theorem
434:
413:edge-transitive
411:) they are not
409:
403:
400:
394:
380:toroidal graphs
368:crossing number
357:
349:
342:
341:For every even
339:
311:
308:
300:
297:
291:
285:
279:
276:circulant graph
258:
257:
253:
250:
246:
224:
220:
209:
201:
194:
191:Edge-transitive
189:
182:
177:
170:
165:
161:
157:
140:
125:Chromatic index
103:
86:
83:
78:
77:
75:
70:
57:
47:
40:
34:
17:
12:
11:
5:
1563:
1561:
1553:
1552:
1550:Regular graphs
1547:
1537:
1536:
1533:
1532:
1511:
1510:External links
1508:
1506:
1505:
1484:
1444:
1427:
1406:
1362:
1306:
1280:(1): 105–119.
1267:
1230:
1210:(2): 179–201.
1193:
1172:
1153:
1133:(4): 493–496.
1109:
1083:(3): 227–245.
1070:
1031:
989:
963:(2): 271–283.
947:
911:(7): 988–991.
898:
872:(3): 425–450.
859:
838:10.1.1.41.8722
831:(3): 326–336.
818:
798:(2): 123–131.
777:
775:
772:
770:
769:
742:
726:
714:
702:
686:
673:
671:
668:
667:
666:
661:
654:
651:
627:
624:
588:
585:
577:Maharry (2000)
558:is called the
555:
548:
537:
515:
504:
501:
486:Petersen graph
481:
475:spanning trees
470:
430:
407:
398:
353:
338:
335:
304:
295:
283:
248:
234:
233:
227:
226:
222:
218:
214:
213:
152:
148:
147:
137:
131:
130:
127:
121:
120:
117:
111:
110:
100:
94:
93:
68:
62:
61:
55:
49:
48:
38:
32:
24:
23:
15:
13:
10:
9:
6:
4:
3:
2:
1562:
1551:
1548:
1546:
1543:
1542:
1540:
1528:
1527:
1522:
1519:
1514:
1513:
1509:
1502:
1498:
1494:
1490:
1485:
1481:
1477:
1473:
1469:
1465:
1461:
1457:
1453:
1449:
1445:
1441:
1437:
1433:
1428:
1424:
1420:
1416:
1412:
1407:
1397:on 2004-01-02
1396:
1392:
1388:
1384:
1380:
1376:
1372:
1368:
1363:
1359:
1355:
1351:
1347:
1343:
1339:
1334:
1329:
1325:
1321:
1320:
1312:
1307:
1303:
1299:
1295:
1291:
1287:
1283:
1279:
1275:
1274:
1268:
1264:
1260:
1255:
1250:
1246:
1242:
1241:
1236:
1231:
1227:
1223:
1218:
1213:
1209:
1205:
1204:
1199:
1194:
1190:
1186:
1182:
1178:
1173:
1168:
1163:
1159:
1154:
1150:
1146:
1141:
1136:
1132:
1128:
1127:
1122:
1118:
1117:Harary, Frank
1114:
1110:
1106:
1102:
1098:
1094:
1090:
1086:
1082:
1078:
1077:
1071:
1067:
1063:
1059:
1055:
1051:
1047:
1043:
1039:
1038:
1032:
1028:
1024:
1020:
1016:
1012:
1008:
1004:
1000:
999:
994:
993:Grötschel, M.
990:
986:
982:
978:
974:
970:
966:
962:
958:
957:
952:
951:Flapan, Erica
948:
944:
940:
936:
932:
928:
924:
919:
914:
910:
906:
905:
899:
895:
891:
887:
883:
879:
875:
871:
867:
866:
860:
856:
852:
848:
844:
839:
834:
830:
826:
825:
819:
815:
811:
806:
801:
797:
793:
792:
787:
783:
779:
778:
773:
767:
763:
759:
755:
751:
746:
743:
739:
735:
730:
727:
723:
718:
715:
711:
706:
703:
699:
698:Valdes (1991)
695:
690:
687:
683:
678:
675:
669:
665:
662:
660:
657:
656:
652:
650:
648:
645:
642:describing a
641:
637:
634:, as part of
633:
625:
623:
621:
616:
614:
610:
606:
602:
598:
593:
586:
584:
582:
578:
574:
571:
567:
566:Gubser (1996)
563:
561:
554:
547:
543:
536:
532:
528:
524:
514:
509:
502:
500:
498:
494:
489:
487:
480:
476:
469:
464:
462:
458:
454:
450:
446:
442:
438:
433:
429:
425:
421:
416:
414:
406:
397:
392:
387:
385:
381:
377:
373:
369:
365:
362:
356:
352:
345:
336:
334:
332:
328:
325: and
324:
320:
314:
307:
303:
294:
290:
289:utility graph
282:
277:
273:
269:
264:
245:
244:Möbius ladder
241:
232:
228:
219:
215:
208:
204:
197:
192:
185:
180:
173:
168:
164:
160:
156:
153:
149:
143:
138:
136:
132:
128:
126:
122:
118:
116:
112:
106:
101:
99:
95:
81:
73:
69:
67:
63:
60:(even number)
56:
54:
50:
45:
37:
30:
25:
22:Möbius ladder
20:
1524:
1492:
1488:
1455:
1451:
1431:
1410:
1399:. Retrieved
1395:the original
1374:
1323:
1317:
1277:
1271:
1244:
1238:
1207:
1206:. Series B.
1201:
1183:(1): 70–80.
1180:
1176:
1130:
1124:
1080:
1074:
1041:
1035:
1002:
996:
960:
954:
908:
902:
869:
868:. Series A.
863:
828:
822:
795:
794:. Series B.
789:
782:Biggs, N. L.
745:
729:
722:Simon (1992)
717:
705:
689:
677:
659:Ladder graph
629:
617:
612:
604:
590:
575:
569:
564:
560:Wagner graph
552:
545:
534:
523:graph minors
520:
512:
503:Graph minors
490:
478:
467:
465:
440:
431:
427:
419:
417:
404:
395:
388:
354:
350:
343:
340:
319:Möbius strip
312:
310:has exactly
305:
301:
292:
280:
243:
240:graph theory
237:
195:
183:
171:
141:
139:1 (for even
104:
102:4 (for even
79:
71:
35:
1458:: 570–590.
1158:Rivin, Igor
664:Prism graph
568:defines an
207:doubly even
1539:Categories
1448:Wagner, K.
1401:2006-10-08
774:References
647:relaxation
542:clique-sum
364:apex graph
337:Properties
181:(for even
169:(for even
151:Properties
1526:MathWorld
1480:123534907
1044:: 43–60.
1027:206798683
1005:: 28–42.
985:119705062
943:119421223
894:206862305
833:CiteSeerX
477:; it and
445:0 (mod 4)
437:bipartite
424:2 (mod 4)
384:Li (2005)
361:nonplanar
205:(for non-
203:Bipartite
159:Circulant
44:this file
1369:(2001).
1358:35931632
1302:46312268
1119:(1967).
1066:21071064
653:See also
640:polytope
473:has 392
268:vertices
217:Notation
179:Toroidal
53:Vertices
1472:1513158
1440:1152127
1423:1196717
1391:2041937
1338:Bibcode
1294:2048553
1263:1609294
1226:1794690
1189:2124859
1149:0224499
1105:7313209
1097:1411084
1058:0809748
1019:0809747
977:0980598
923:Bibcode
886:1782150
855:1710240
814:0294172
599: (
529: (
451:it has
439:. When
329: (
90:
76:
1478:
1470:
1438:
1421:
1389:
1356:
1300:
1292:
1261:
1224:
1187:
1147:
1103:
1095:
1064:
1056:
1025:
1017:
983:
975:
941:
892:
884:
853:
835:
812:
609:chiral
597:Flapan
346:> 4
327:Harary
242:, the
198:= 4, 6
186:> 4
174:> 4
144:> 4
107:> 4
1476:S2CID
1354:S2CID
1328:arXiv
1314:(PDF)
1298:S2CID
1162:arXiv
1101:S2CID
1062:S2CID
1023:S2CID
981:S2CID
939:S2CID
913:arXiv
890:S2CID
762:1985b
758:1985a
670:Notes
418:When
372:torus
359:is a
287:(the
272:cubic
263:cycle
193:(for
155:Cubic
135:Genus
98:Girth
66:Edges
601:1989
581:cube
531:1937
491:The
402:and
331:1967
167:Apex
1497:doi
1493:104
1460:doi
1456:114
1379:doi
1346:doi
1282:doi
1249:doi
1245:184
1212:doi
1135:doi
1085:doi
1046:doi
1007:doi
965:doi
961:283
931:doi
874:doi
843:doi
800:doi
764:);
455:3.
435:is
374:or
333:).
323:Guy
299:),
296:3,3
238:In
1541::
1523:.
1491:.
1474:.
1468:MR
1466:.
1454:.
1436:MR
1419:MR
1387:MR
1385:.
1373:.
1352:.
1344:.
1336:.
1324:57
1322:.
1316:.
1296:.
1290:MR
1288:.
1278:20
1276:.
1259:MR
1257:.
1243:.
1237:.
1222:MR
1220:.
1208:80
1200:.
1185:MR
1181:21
1179:.
1145:MR
1143:.
1131:10
1129:.
1123:.
1115:;
1099:.
1093:MR
1091:.
1079:.
1060:.
1054:MR
1052:.
1042:33
1040:.
1021:.
1015:MR
1013:.
1003:33
1001:.
979:.
973:MR
971:.
959:.
937:.
929:.
921:.
909:19
907:.
888:.
882:MR
880:.
870:88
851:MR
849:.
841:.
829:12
827:.
810:MR
808:.
796:12
788:.
760:,
752:;
736:;
696:;
562:.
499:.
463:.
443:≡
426:,
422:≡
382:.
315:/2
274:,
74:+
39:16
1529:.
1503:.
1499::
1482:.
1462::
1442:.
1425:.
1404:.
1381::
1360:.
1348::
1340::
1330::
1304:.
1284::
1265:.
1251::
1228:.
1214::
1191:.
1170:.
1164::
1151:.
1137::
1107:.
1087::
1081:5
1068:.
1048::
1029:.
1009::
987:.
967::
945:.
933::
925::
915::
896:.
876::
857:.
845::
816:.
802::
740:.
724:.
712:.
700:.
684:.
613:R
605:R
556:8
553:M
549:8
546:M
538:5
535:K
516:8
513:M
482:6
479:M
471:8
468:M
441:n
432:n
428:M
420:n
408:6
405:M
399:4
396:M
355:n
351:M
344:n
313:n
306:n
302:M
293:K
284:6
281:M
261:-
259:n
254:n
249:n
247:M
223:n
221:M
212:)
210:n
200:)
196:n
188:)
184:n
176:)
172:n
146:)
142:n
129:3
119:3
109:)
105:n
87:2
84:/
80:n
72:n
58:n
46:.
36:M
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
