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