35:
252:
378:
27:
78:
that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a
Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such
924:
of its weighted adjacency matrix defined as the sum of the products of the arc weights of the digraph's
Hamiltonian cycles. This polynomial is not identically zero as a function in the arc weights if and only if the digraph is Hamiltonian. The relationship between the computational complexities of
34:
848:
The number of vertices must be doubled because each undirected edge corresponds to two directed arcs and thus the degree of a vertex in the directed graph is twice the degree in the undirected graph.
393:
Any
Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a Hamiltonian path can be extended to a Hamiltonian cycle only if its endpoints are adjacent.
436:, so the line graph of every Eulerian graph is Hamiltonian. Line graphs may have other Hamiltonian cycles that do not correspond to Euler tours, and in particular the line graph
705:
229:, where each edge (arc) of a path or cycle can only be traced in a single direction (i.e., the vertices are connected with arrows and the edges traced "tail-to-head").
753:
676:
282:
843:
634:
As complete graphs are
Hamiltonian, all graphs whose closure is complete are Hamiltonian, which is the content of the following earlier theorems by Dirac and Ore.
885:, in which the vertex degrees are compared to the number of vertices on a single side of the bipartition rather than the number of vertices in the whole graph.
1609:
920:
An algebraic representation of the
Hamiltonian cycles of a given weighted digraph (whose arcs are assigned weights from a certain ground field) is the
1211:
Gardner, M. "Mathematical Games: About the
Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957
1849:
870:
vertices has a
Hamiltonian path if, for every non-adjacent vertex pairs the sum of their degrees and their shortest path length is greater than
19:
This article is about the nature of
Hamiltonian paths. For the question of the existence of a Hamiltonian path or cycle in a given graph, see
275:
1834:
1055:
129:, who, in particular, gave an example of a polyhedron without Hamiltonian cycles. Even earlier, Hamiltonian cycles and paths in the
268:
1698:
816:
vertices is
Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to
1864:
1149:
1222:
Ghaderpour, E.; Morris, D. W. (2014). "Cayley graphs on nilpotent groups with cyclic commutator subgroup are
Hamiltonian".
1189:
1369:
1568:
1352:
1551:
Kogan, Grigoriy (1996). "Computing permanents over fields of characteristic 3: Where and why it becomes difficult".
1624:
1298:
1869:
1714:
878:
The above theorem can only recognize the existence of a Hamiltonian path in a graph and not a Hamiltonian Cycle.
507:. These counts assume that cycles that are the same apart from their starting point are not counted separately.
418:
in which every vertex has even degree) necessarily has an Euler tour, a closed walk passing through each edge of
1034:
1859:
1854:
1433:
150:
1785:
1712:
Meyniel, M. (1973), "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté",
125:
Despite being named after Hamilton, Hamiltonian cycles in polyhedra had also been studied a year earlier by
921:
463:
1084:
185:
that visits each vertex of the graph exactly once. A graph that contains a Hamiltonian path is called a
555:
among other parameters. Dirac and Ore's theorems basically state that a graph is Hamiltonian if it has
548:
243:
is a type of logic puzzle in which the goal is to find the unique Hamiltonian cycle in a given graph.
681:
459:
310:
233:
981:
939:
803:
774:
84:
20:
1016:
957:
926:
552:
539:(1962). Hamiltonicity has been widely studied with relation to various parameters such as graph
1693:
1679:
1674:
91:
1342:
1296:; Noy, Marc (1999), "Graph of triangulations of a convex polygon and tree of triangulations",
987:
971:
732:
655:
516:
63:
1210:
216:
that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a
1801:
1777:
1737:
1666:
1642:
1507:
1454:
1126:
1074:
1064:
528:
213:
75:
1012:
819:
755:) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is
336:
314:
8:
1400:
Rahman, M. S.; Kaykobad, M. (April 2005). "On Hamiltonian cycles and Hamiltonian paths".
524:
350:
182:
111:
59:
1765:
1574:
1495:
1458:
1249:
1231:
1039:
256:
142:
1820:
1537:
1312:
1817:
1728:
1564:
1462:
1348:
1327:
1280:
1145:
997:
854:
397:
335:
is Hamiltonian (For more information on Hamiltonian paths in Cayley graphs, see the
158:
130:
122:(also invented by Hamilton). This solution does not generalize to arbitrary graphs.
1578:
1253:
193:
if for every pair of vertices there is a Hamiltonian path between the two vertices.
1757:
1723:
1654:
1556:
1532:
1487:
1442:
1409:
1307:
1276:
1241:
1114:
1078:
1045:
993:
946:
787:
vertices is Hamiltonian if every vertex has a full degree greater than or equal to
713:
386:
138:
107:
1797:
1773:
1733:
1662:
1503:
1475:
1450:
1181:
1122:
1028:
1022:
943:
882:
544:
415:
346:
154:
536:
1376:
1293:
1245:
1042:, a numerical measure of how far from Hamiltonian the graphs in a family can be
990:, a non-Hamiltonian graph in which every vertex-deleted subgraph is Hamiltonian
961:
809:
780:
408:
401:
382:
321:
296:
259:
of the vertices of the five platonic solids – only the octahedron has an
225:
162:
126:
1745:
1413:
532:
251:
1843:
1658:
1560:
1059:
951:
469:
The number of different Hamiltonian cycles in a complete undirected graph on
389:
that does not have a Hamiltonian cycle. A possible Hamiltonian path is shown.
361:
332:
260:
115:
1267:
Lucas, Joan M. (1987), "The rotation graph of binary trees is Hamiltonian",
377:
1596:
1118:
1068:
1049:
1002:
975:
863:
806:
777:
722:
645:
342:
328:
103:
95:
47:
1520:
1006:
590:
540:
520:
400:, but a biconnected graph need not be Hamiltonian (see, for example, the
365:
303:
80:
43:
1769:
1499:
1446:
423:
357:
134:
119:
102:, which involves finding a Hamiltonian cycle in the edge graph of the
1825:
1428:
966:
1761:
1491:
1031:, a strengthening of both pancyclicity and Hamiltonian-connectedness
888:
519:
characterization of Hamiltonian graphs was provided in 1972 by the
1236:
630:
A graph is Hamiltonian if and only if its closure is Hamiltonian.
462:(with more than two vertices) is Hamiltonian if and only if it is
422:
exactly once. This tour corresponds to a Hamiltonian cycle in the
1553:
Proceedings of 37th Conference on Foundations of Computer Science
1025:, graphs with cycles of all lengths including a Hamiltonian cycle
146:
1677:(1856), "Memorandum respecting a new system of roots of unity",
236:
is an edge decomposition of a graph into Hamiltonian circuits.
26:
1341:
Balakrishnan, R.; Ranganathan, K. (2012), "Corollary 6.5.5",
763:
The following theorems can be regarded as directed versions:
900:
A 4-connected planar triangulation has a Hamiltonian cycle.
535:. Both Dirac's and Ore's theorems can also be derived from
157:. In 18th century Europe, knight's tours were published by
1815:
1610:"A study of sufficient conditions for Hamiltonian cycles"
38:
Examples of Hamiltonian cycles on a square grid graph 8x8
1142:
Across the Board: The Mathematics of Chessboard Problems
984:, the computational problem of finding Hamiltonian paths
1340:
451:
is itself Hamiltonian, regardless of whether the graph
1140:
Watkins, John J. (2004), "Chapter 2: Knight's Tours",
686:
1105:
Biggs, N. L. (1981), "T. P. Kirkman, mathematician",
822:
735:
684:
658:
620:
until no more pairs with this property can be found.
911:
A 4-connected planar graph has a Hamiltonian cycle.
263:
or cycle, by extending its path with the dotted one
255:
Orthographic projections and Schlegel diagrams with
62:
in an undirected or directed graph that visits each
30:
A Hamiltonian cycle around a network of six vertices
16:
Path in a graph that visits each vertex exactly once
1595:
915:
583:vertices, obtained by repeatedly adding a new edge
881:Many of these results have analogues for balanced
837:
747:
699:
670:
1841:
1370:"Advances on the Hamiltonian Problem – A Survey"
1221:
889:Existence of Hamiltonian cycles in planar graphs
1788:(1962), "A theorem concerning Hamilton lines",
1107:The Bulletin of the London Mathematical Society
1647:Proceedings of the London Mathematical Society
1601:Programming, games and transportation networks
1399:
1144:, Princeton University Press, pp. 25–38,
527:theorem, which generalizes earlier results by
276:
90:Hamiltonian paths and cycles are named after
1645:(1952), "Some theorems on abstract graphs",
942:, an open problem on Hamiltonicity of cubic
678:) is Hamiltonian if every vertex has degree
1696:(1858), "Account of the Icosian Calculus",
1431:(1963), "On Hamiltonian bipartite graphs",
1325:
1292:
562:The Bondy–Chvátal theorem operates on the
299:with more than two vertices is Hamiltonian
283:
269:
106:. Hamilton solved this problem using the
1727:
1536:
1426:
1311:
1235:
1164:
360:of a convex polygon or equivalently, the
141:, had been studied in the 9th century in
1790:Magyar Tud. Akad. Mat. Kutató Int. Közl.
1692:
1673:
1179:
510:
376:
313:has an odd number of Hamiltonian paths (
250:
33:
25:
1711:
1474:
1139:
324:, considered as a graph, is Hamiltonian
1850:Computational problems in graph theory
1842:
1699:Proceedings of the Royal Irish Academy
1617:Rose-Hulman Undergraduate Math Journal
1607:
1523:(1956), "A theorem on planar graphs",
1816:
1748:(1960), "Note on Hamilton circuits",
1641:
1550:
1519:
1367:
1266:
1167:Hamilton Mazes – The Beginner's Guide
1104:
954:, a path through all edges in a graph
79:paths and cycles exist in graphs are
1784:
1058:for finding a Hamiltonian path in a
495:and in a complete directed graph on
1744:
1056:Steinhaus–Johnson–Trotter algorithm
223:Similar notions may be defined for
13:
1375:. Emory University. Archived from
1192:from the original on 16 April 2016
14:
1881:
1809:
1750:The American Mathematical Monthly
1538:10.1090/s0002-9947-1956-0081471-8
1368:Gould, Ronald J. (July 8, 2002).
1077:(now known false) that 3-regular
974:giving a necessary condition for
916:The Hamiltonian cycle polynomial
1715:Journal of Combinatorial Theory
1544:
1513:
1478:(1931), "A theorem on graphs",
1468:
1420:
1393:
1361:
1334:
700:{\displaystyle {\tfrac {n}{2}}}
1835:Euler tour and Hamilton cycles
1402:Information Processing Letters
1319:
1286:
1260:
1215:
1204:
1173:
1158:
1133:
1098:
168:
149:, and around the same time in
118:with many similarities to the
1:
1599:; Ghouila-Houiri, A. (1962),
1589:
1434:Israel Journal of Mathematics
1313:10.1016/S0925-7721(99)00016-4
1224:Ars Mathematica Contemporanea
996:, a Hamiltonian cycle in the
929:was shown by Grigoriy Kogan.
372:
1865:Hamiltonian paths and cycles
1729:10.1016/0095-8956(73)90057-9
1281:10.1016/0196-6774(87)90048-4
922:Hamiltonian cycle polynomial
625:Bondy–Chvátal Theorem (1976)
7:
1085:Travelling salesman problem
1035:Seven Bridges of Königsberg
978:to have a Hamiltonian cycle
932:
447:of every Hamiltonian graph
396:All Hamiltonian graphs are
246:
10:
1886:
1344:A Textbook of Graph Theory
1246:10.26493/1855-3974.280.8d3
18:
1414:10.1016/j.ipl.2004.12.002
1347:, Springer, p. 134,
1165:de Ruiter, Johan (2017).
385:is the smallest possible
234:Hamiltonian decomposition
1608:DeLeon, Melissa (2000),
1561:10.1109/SFCS.1996.548469
1180:Friedman, Erich (2009).
1091:
1017:vertex-transitive graphs
982:Hamiltonian path problem
85:Hamiltonian path problem
21:Hamiltonian path problem
1694:Hamilton, William Rowan
1675:Hamilton, William Rowan
1525:Trans. Amer. Math. Soc.
927:computing the permanent
748:{\displaystyle n\geq 3}
671:{\displaystyle n\geq 3}
1870:William Rowan Hamilton
1680:Philosophical Magazine
1659:10.1112/plms/s3-2.1.69
1603:, New York: Sons, Inc.
1299:Computational Geometry
839:
749:
701:
672:
639:Dirac's Theorem (1952)
390:
291:
92:William Rowan Hamilton
39:
31:
1480:Annals of Mathematics
1269:Journal of Algorithms
1186:Erich's Puzzle Palace
988:Hypohamiltonian graph
940:Barnette's conjecture
840:
768:Ghouila–Houiri (1960)
750:
702:
673:
511:Bondy–Chvátal theorem
380:
254:
191:Hamiltonian-connected
37:
29:
1860:Graph theory objects
1855:NP-complete problems
1555:. pp. 108–114.
1330:. Wolfram MathWorld.
1119:10.1112/blms/13.2.97
1065:Subhamiltonian graph
958:Fleischner's theorem
838:{\displaystyle 2n-1}
820:
733:
682:
656:
98:, now also known as
1821:"Hamiltonian Cycle"
1623:(1), archived from
1328:"Biconnected Graph"
1182:"Hamiltonian Mazes"
909: —
898: —
860: —
800: —
771: —
719: —
642: —
628: —
549:forbidden subgraphs
351:commutator subgroup
202:Hamiltonian circuit
151:Islamic mathematics
112:algebraic structure
94:, who invented the
72:Hamiltonian circuit
1818:Weisstein, Eric W.
1447:10.1007/BF02759704
1067:, a subgraph of a
1040:Shortness exponent
972:Grinberg's theorem
907:
896:
858:
835:
804:strongly connected
798:
775:strongly connected
769:
745:
717:
697:
695:
668:
640:
626:
464:strongly connected
391:
292:
257:Hamiltonian cycles
143:Indian mathematics
40:
32:
1482:, Second Series,
1151:978-0-691-15498-5
1079:polyhedral graphs
1075:Tait's conjecture
1071:Hamiltonian graph
1013:Lovász conjecture
962:squares of graphs
960:, on Hamiltonian
947:polyhedral graphs
925:computing it and
905:
894:
852:
796:
767:
712:
694:
638:
624:
593:pair of vertices
368:, is Hamiltonian.
337:Lovász conjecture
218:Hamiltonian graph
198:Hamiltonian cycle
159:Abraham de Moivre
100:Hamilton's puzzle
68:Hamiltonian cycle
1877:
1831:
1830:
1804:
1780:
1740:
1731:
1707:
1688:
1669:
1637:
1636:
1635:
1629:
1614:
1604:
1583:
1582:
1548:
1542:
1541:
1540:
1517:
1511:
1510:
1476:Whitney, Hassler
1472:
1466:
1465:
1424:
1418:
1417:
1397:
1391:
1390:
1388:
1387:
1381:
1374:
1365:
1359:
1357:
1338:
1332:
1331:
1326:Eric Weinstein.
1323:
1317:
1316:
1315:
1290:
1284:
1283:
1264:
1258:
1257:
1239:
1219:
1213:
1208:
1202:
1201:
1199:
1197:
1177:
1171:
1170:
1162:
1156:
1154:
1137:
1131:
1129:
1102:
1046:Snake-in-the-box
1005:for Hamiltonian
910:
899:
883:bipartite graphs
873:
869:
861:
844:
842:
841:
836:
815:
801:
790:
786:
772:
758:
754:
752:
751:
746:
728:
720:
706:
704:
703:
698:
696:
687:
677:
675:
674:
669:
651:
643:
629:
619:
604:
598:
588:
582:
578:
572:
515:The best vertex
506:
498:
494:
493:
491:
490:
487:
484:
472:
454:
450:
446:
435:
421:
413:
387:polyhedral graph
353:are Hamiltonian.
347:nilpotent groups
290:
285:
278:
271:
175:Hamiltonian path
108:icosian calculus
66:exactly once. A
52:Hamiltonian path
1885:
1884:
1880:
1879:
1878:
1876:
1875:
1874:
1840:
1839:
1812:
1762:10.2307/2308928
1633:
1631:
1627:
1612:
1592:
1587:
1586:
1571:
1549:
1545:
1518:
1514:
1492:10.2307/1968197
1473:
1469:
1425:
1421:
1398:
1394:
1385:
1383:
1379:
1372:
1366:
1362:
1355:
1339:
1335:
1324:
1320:
1294:Hurtado, Ferran
1291:
1287:
1265:
1261:
1220:
1216:
1209:
1205:
1195:
1193:
1178:
1174:
1163:
1159:
1152:
1138:
1134:
1103:
1099:
1094:
1089:
1081:are Hamiltonian
1029:Panconnectivity
1023:Pancyclic graph
1019:are Hamiltonian
935:
918:
913:
908:
902:
897:
891:
876:
871:
867:
859:
846:
821:
818:
817:
813:
799:
793:
788:
784:
770:
761:
756:
734:
731:
730:
726:
718:
709:
685:
683:
680:
679:
657:
654:
653:
649:
641:
632:
627:
606:
600:
594:
584:
580:
574:
566:
513:
500:
496:
488:
485:
478:
477:
475:
474:
470:
452:
448:
437:
426:
419:
416:connected graph
411:
375:
289:
264:
249:
226:directed graphs
187:traceable graph
171:
155:al-Adli ar-Rumi
24:
17:
12:
11:
5:
1883:
1873:
1872:
1867:
1862:
1857:
1852:
1838:
1837:
1832:
1811:
1810:External links
1808:
1807:
1806:
1782:
1742:
1722:(2): 137–147,
1709:
1690:
1671:
1639:
1605:
1591:
1588:
1585:
1584:
1569:
1543:
1512:
1486:(2): 378–390,
1467:
1441:(3): 163–165,
1419:
1392:
1360:
1353:
1333:
1318:
1306:(3): 179–188,
1285:
1275:(4): 503–535,
1259:
1214:
1203:
1172:
1157:
1150:
1132:
1096:
1095:
1093:
1090:
1088:
1087:
1082:
1072:
1062:
1053:
1052:in a hypercube
1048:, the longest
1043:
1037:
1032:
1026:
1020:
1010:
1000:
998:knight's graph
991:
985:
979:
969:
964:
955:
949:
936:
934:
931:
917:
914:
903:
892:
890:
887:
850:
834:
831:
828:
825:
810:directed graph
797:Meyniel (1973)
794:
781:directed graph
765:
744:
741:
738:
710:
693:
690:
667:
664:
661:
636:
622:
537:Pósa's theorem
512:
509:
409:Eulerian graph
402:Petersen graph
383:Herschel graph
374:
371:
370:
369:
362:rotation graph
354:
340:
325:
322:platonic solid
318:
307:
306:is Hamiltonian
300:
297:complete graph
288:
287:
280:
273:
265:
248:
245:
179:traceable path
170:
167:
163:Leonhard Euler
131:knight's graph
127:Thomas Kirkman
116:roots of unity
56:traceable path
15:
9:
6:
4:
3:
2:
1882:
1871:
1868:
1866:
1863:
1861:
1858:
1856:
1853:
1851:
1848:
1847:
1845:
1836:
1833:
1828:
1827:
1822:
1819:
1814:
1813:
1803:
1799:
1795:
1791:
1787:
1783:
1779:
1775:
1771:
1767:
1763:
1759:
1755:
1751:
1747:
1743:
1739:
1735:
1730:
1725:
1721:
1717:
1716:
1710:
1705:
1701:
1700:
1695:
1691:
1686:
1682:
1681:
1676:
1672:
1668:
1664:
1660:
1656:
1652:
1648:
1644:
1640:
1630:on 2012-12-22
1626:
1622:
1618:
1611:
1606:
1602:
1598:
1597:Berge, Claude
1594:
1593:
1580:
1576:
1572:
1570:0-8186-7594-2
1566:
1562:
1558:
1554:
1547:
1539:
1534:
1530:
1526:
1522:
1516:
1509:
1505:
1501:
1497:
1493:
1489:
1485:
1481:
1477:
1471:
1464:
1460:
1456:
1452:
1448:
1444:
1440:
1436:
1435:
1430:
1423:
1415:
1411:
1407:
1403:
1396:
1382:on 2018-07-13
1378:
1371:
1364:
1356:
1354:9781461445296
1350:
1346:
1345:
1337:
1329:
1322:
1314:
1309:
1305:
1301:
1300:
1295:
1289:
1282:
1278:
1274:
1270:
1263:
1255:
1251:
1247:
1243:
1238:
1233:
1229:
1225:
1218:
1212:
1207:
1191:
1187:
1183:
1176:
1168:
1161:
1153:
1147:
1143:
1136:
1128:
1124:
1120:
1116:
1113:(2): 97–120,
1112:
1108:
1101:
1097:
1086:
1083:
1080:
1076:
1073:
1070:
1066:
1063:
1061:
1060:permutohedron
1057:
1054:
1051:
1047:
1044:
1041:
1038:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1014:
1011:
1008:
1004:
1001:
999:
995:
994:Knight's tour
992:
989:
986:
983:
980:
977:
976:planar graphs
973:
970:
968:
965:
963:
959:
956:
953:
952:Eulerian path
950:
948:
945:
941:
938:
937:
930:
928:
923:
912:
901:
886:
884:
879:
875:
865:
856:
849:
845:
832:
829:
826:
823:
811:
808:
805:
792:
782:
779:
776:
764:
760:
742:
739:
736:
724:
715:
714:Ore's Theorem
708:
691:
688:
665:
662:
659:
647:
635:
631:
621:
618:
614:
610:
603:
597:
592:
589:connecting a
587:
577:
570:
565:
560:
558:
554:
550:
546:
542:
538:
534:
530:
526:
522:
518:
508:
504:
482:
467:
465:
461:
456:
455:is Eulerian.
444:
440:
433:
429:
425:
417:
410:
405:
403:
399:
394:
388:
384:
379:
367:
363:
359:
355:
352:
348:
344:
343:Cayley graphs
341:
338:
334:
333:Coxeter group
330:
326:
323:
319:
316:
312:
308:
305:
301:
298:
294:
293:
286:
281:
279:
274:
272:
267:
266:
262:
261:Eulerian path
258:
253:
244:
242:
241:Hamilton maze
237:
235:
230:
228:
227:
221:
219:
215:
211:
207:
203:
199:
194:
192:
189:. A graph is
188:
184:
180:
176:
166:
164:
160:
156:
152:
148:
144:
140:
139:knight's tour
136:
132:
128:
123:
121:
117:
113:
109:
105:
101:
97:
93:
88:
87:for details.
86:
82:
77:
73:
69:
65:
61:
57:
53:
49:
45:
36:
28:
22:
1824:
1793:
1789:
1753:
1749:
1746:Ore, Øystein
1719:
1718:, Series B,
1713:
1703:
1697:
1684:
1678:
1650:
1649:, 3rd Ser.,
1646:
1643:Dirac, G. A.
1632:, retrieved
1625:the original
1620:
1616:
1600:
1552:
1546:
1528:
1524:
1521:Tutte, W. T.
1515:
1483:
1479:
1470:
1438:
1432:
1422:
1405:
1401:
1395:
1384:. Retrieved
1377:the original
1363:
1343:
1336:
1321:
1303:
1297:
1288:
1272:
1268:
1262:
1230:(1): 55–72.
1227:
1223:
1217:
1206:
1194:. Retrieved
1185:
1175:
1166:
1160:
1141:
1135:
1110:
1106:
1100:
1050:induced path
1007:cubic graphs
1003:LCF notation
919:
904:
893:
880:
877:
864:simple graph
851:
847:
795:
766:
762:
759:or greater.
723:simple graph
711:
707:or greater.
646:simple graph
637:
633:
623:
616:
612:
608:
601:
595:
585:
575:
568:
563:
561:
557:enough edges
556:
514:
502:
499:vertices is
480:
473:vertices is
468:
457:
442:
438:
431:
427:
406:
395:
392:
366:binary trees
349:with cyclic
331:of a finite
329:Cayley graph
240:
238:
231:
224:
222:
217:
209:
205:
201:
197:
195:
190:
186:
178:
174:
172:
124:
104:dodecahedron
99:
96:icosian game
89:
71:
67:
55:
51:
48:graph theory
44:mathematical
41:
1796:: 225–226,
591:nonadjacent
573:of a graph
533:Øystein Ore
531:(1952) and
529:G. A. Dirac
398:biconnected
304:cycle graph
210:graph cycle
206:vertex tour
169:Definitions
120:quaternions
81:NP-complete
1844:Categories
1634:2005-11-28
1590:References
1531:: 99–116,
1427:Moon, J.;
1386:2012-12-10
729:vertices (
652:vertices (
460:tournament
424:line graph
373:Properties
358:flip graph
311:tournament
135:chessboard
1826:MathWorld
1756:(1): 55,
1706:: 415–416
1653:: 69–81,
1463:119358798
1429:Moser, L.
1408:: 37–41.
1237:1111.6216
967:Gray code
944:bipartite
830:−
740:≥
663:≥
545:toughness
114:based on
46:field of
1786:Pósa, L.
1579:39024286
1254:57575227
1190:Archived
933:See also
855:Kaykobad
611:) + deg(
553:distance
247:Examples
1802:0184876
1778:0118683
1770:2308928
1738:0317997
1667:0047308
1508:1503003
1500:1968197
1455:0161332
1127:0608093
906:Theorem
895:Theorem
853:Rahman–
564:closure
541:density
525:Chvátal
492:
476:
147:Rudrata
133:of the
74:) is a
58:) is a
42:In the
1800:
1776:
1768:
1736:
1665:
1577:
1567:
1506:
1498:
1461:
1453:
1351:
1252:
1196:27 May
1148:
1125:
1069:planar
857:(2005)
807:simple
778:simple
716:(1960)
517:degree
320:Every
309:Every
302:Every
137:, the
83:; see
64:vertex
1766:JSTOR
1687:: 446
1628:(PDF)
1613:(PDF)
1575:S2CID
1496:JSTOR
1459:S2CID
1380:(PDF)
1373:(PDF)
1250:S2CID
1232:arXiv
1092:Notes
1015:that
866:with
812:with
783:with
725:with
648:with
605:with
579:with
521:Bondy
505:– 1)!
483:– 1)!
317:1934)
315:Rédei
214:cycle
212:is a
181:is a
110:, an
76:cycle
1565:ISBN
1349:ISBN
1198:2017
1146:ISBN
615:) ≥
607:deg(
599:and
551:and
381:The
356:The
327:The
183:path
161:and
70:(or
60:path
54:(or
50:, a
1758:doi
1724:doi
1655:doi
1557:doi
1533:doi
1488:doi
1443:doi
1410:doi
1308:doi
1277:doi
1242:doi
1115:doi
567:cl(
414:(a
407:An
404:).
364:of
345:on
208:or
177:or
153:by
145:by
1846::
1823:.
1798:MR
1792:,
1774:MR
1772:,
1764:,
1754:67
1752:,
1734:MR
1732:,
1720:14
1702:,
1685:12
1683:,
1663:MR
1661:,
1619:,
1615:,
1573:.
1563:.
1529:82
1527:,
1504:MR
1502:,
1494:,
1484:32
1457:,
1451:MR
1449:,
1437:,
1406:94
1404:.
1304:13
1302:,
1271:,
1248:.
1240:.
1226:.
1188:.
1184:.
1123:MR
1121:,
1111:13
1109:,
874:.
862:A
802:A
791:.
773:A
721:A
644:A
586:uv
559:.
547:,
543:,
466:.
458:A
339:.)
295:A
239:A
232:A
220:.
204:,
200:,
196:A
173:A
165:.
1829:.
1805:.
1794:7
1781:.
1760::
1741:.
1726::
1708:.
1704:6
1689:.
1670:.
1657::
1651:2
1638:.
1621:1
1581:.
1559::
1535::
1490::
1445::
1439:1
1416:.
1412::
1389:.
1358:.
1310::
1279::
1273:8
1256:.
1244::
1234::
1228:7
1200:.
1169:.
1155:.
1130:.
1117::
1009:.
872:n
868:n
833:1
827:n
824:2
814:n
789:n
785:n
757:n
743:3
737:n
727:n
692:2
689:n
666:3
660:n
650:n
617:n
613:u
609:v
602:v
596:u
581:n
576:G
571:)
569:G
523:–
503:n
501:(
497:n
489:2
486:/
481:n
479:(
471:n
453:G
449:G
445:)
443:G
441:(
439:L
434:)
432:G
430:(
428:L
420:G
412:G
284:e
277:t
270:v
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
