264:
1189:
254:
233:
200:
1177:
1165:
1150:
1114:
1090:
1126:
1078:
1138:
1102:
191:
626:
an H. Path is
Hamiltonian. Because not all authors define the term Hamiltonian equally, we should remove the term and replace it with a clearer phrase. I recommend we edit the second reference to tournaments to read "A tournament with more than two vertices has a Hamiltonian Circuit if and only if it
342:
The starting paragraph contains a wrong definition. As it is defined now, any graph contains a
Hamiltonian path (e.g., the empty path, or a single edge between two vertices). The reason is that it only requires the path to visit each vertex *in the path* once; it doesn't require that each *and every*
1227:
No, I think it's correct. The point is that by adding edges between pairs of vertices for which the degree inequality is already true, you can make the inequality true for other pairs as well. And it shouldn't have an effect on sparse graphs, because many of those are non-Hamiltonian and it would be
897:
I think it makes sense on heavily studied problems (including clique and
Hamiltonian paths) to have separate articles about the mathematics of the problem (results about cliques that do not involve algorithms, of which there are many) and the computer science of the problem (algorithms for computing
1248:
The topic of a
Hamiltonian decomposition (partition of edges into Hamiltonian circuits) is broached in the article, but nothing of substance is said about e.g. conditions for existence of such. Possibly this deserves its own article; an early (19th century) result in graph theory is the theorem of
669:
As an example, this is perfectly fine. People who are trying to learn about
Hamiltonian Circuits can look at platonic solids and attempt to find the circuits in question. Additionally, because of the historic context, i.e. Hamilton's dodecahedron game, I recommend we keep it. It's an example, not a
989:
I'm not sure these belong on this page. Whether they perform properly is one question, Whether they are original research is yet another. Also, since the algorithms in question came from other forums there is a question of copyright. I suggest removing them to this talk page.
512:
I think we might need a better example image - at first I just stared at the image unsure what to look for. After refreshing my memory I noticed that the black line was actually the path travelled. I slighly updated the description, but I think we need a better example here.
885:
I just removed the merger templates five days ago; after they had been around since
December 2009. :-) I disagree with the merger; the articles look sufficiently long to me (with scope for further expansion). This was proposed and discussed before at
621:
is right. These statements seem at odds with one another, but that is because one seems to be speaking about Paths and the other
Circuits. Some authors say a graph with an H. Circuit is Hamiltonian, while others say a graph containing an H. Circuit
153:
385:
interpretation. Icosian
Calculus involves roots with different exponents and not requiring the distributive property of multiplication. In these calculuations, values entering only as connecting exponents and not as connecting terms.
430:
I think it might make more sense to talk about this as part of the history, since
Hamilton's icosian calculus doesn't have much to do with the hamiltionian path problem as studied today. I will try to come up with something.
843:
Should we replace "Hamiltonian" in the theorems with "contains a
Hamiltonian circuit"? This would clarify the article quite a bit, while leaving "Hamiltonian" defined for those who wish to use it or discover its meaning.
818:, and should be defined here. "Hamiltonian circuit" and "Hamiltonian path" have too much in common to each have their own articles. I think we should simply work to clarify the confusing parts of the existing article.
347:-- Indeed you are correct. This is an incorrect definition; otherwise, the statement: "Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete." is incorrect!
1209:
edges (nor does this procedure have any effect if you start with a graph with a small number of edges). Most likely the sense of the inequality is backwards. Someone who knows a reference on this should fix it.
798:. I recommend either we discuss Paths and Circuits on separate pages, or remove the definition "Hamiltonian graph" and ensure that all theorems state instead, that a graph "contains a Hamiltonian circuit".
1204:
the definition of "closure" given in the section on the Bondy-Chvatal theorem obviously isn't the right one. Obviously, because you cannot create a situation where the degree inequality fails to hold by
1275:
is one that visits every edge, whereas a Hamiltonian path is one that visits every vertex. Do you think the expected reader might accidentally confuse the two? Just wanted to ask cos I wasn't certain.
497:
who originated the concept of the knight's tour on a chessboard. I don't think this term is widespread enough yet to be worth including in the article, but it may be worth thinking about in future.
147:
670:
Theorem. If it does generalize, then we should add that as a theorem. I also recommend changing the phrase to read "Every platonic solid, considered as a graph, contains a Hamiltonian Circuit."
790:, readers who read only part of the definitions section will be confused, and may leave with misinformation if they assume that "Hamiltonian graph" means a graph that contains a Hamiltonian
365:
Guys, the definition or statements of NP-hardness are incorrect. If the Hamiltonian path doesn't visit ALL vertices, it is surely not NP-hard (just output the empty path, or a single edge).
320:
1318:
1005:
This can be safely removed, and not only for the reasons you state. Algorithms that solve “a subset” of the instances, in particular if that subset is ill defined, are not noteworthy.
1188:
567:
commented on tries to do so, but is confusing since it could easily be made into a Hamiltonian Circuit. We should replace the old image with an image containing a graph that does
887:
1025:
There are "citation needed" tags on the claims that all prism and antiprism graphs are Hamiltonian. Is that really necessary? These claims seem easily verified by the reader.
969:
to clarify the different focuses. If anyone has neater wording feel free to edit these. Of course, we also need to rewrite both articles to better reflect these focuses.
1308:
1249:
Walecki shows a complete graph on an odd number of vertices has a Hamiltonian decomposition. At a glance no mention of this appears in any Knowledge article, yet.
647:"every platonic solid, considered as a graph, is Hamiltonian". Since there are only 5 platonic solids this is rather uninteresting. Does the result generalize to
1323:
204:
1333:
310:
168:
79:
135:
1303:
571:
contain a Hamiltonian cirucit, but has a Hamiltonian path. The two are distinct concepts that can be clearly exemplified by a wise choice of images.
1149:
782:, the use of the term "Hamiltonian Graph" is misleading and confusing. Because this page introduces two distinct but similar ideas, the Hamiltonian
44:
1313:
286:
1328:
85:
1176:
129:
1213:
1164:
828:
1113:
750:
as being the sum of in and out degrees of a vertex. I haven't the foggiest how this might be made more clear, but it sorely needs to be.
898:
cliques, of which there are many). I think the right thing to do in the long term for clique is similarly to have two or three articles
447:- Offer prize of one million dollars promised to those who solve the seven problems unsolved at the end of 20th century, one being the
125:
697:
652:
541:
I added an example I found on the German Knowledge article. Maybe the other one should be removed, it seems somewhat hard to follow.
348:
277:
238:
175:
1298:
563:
is a good example of a Hamiltonian Circuit, but there is no image of a non-circuitous Hamiltonian path. The orignal image that
99:
30:
1060:
In case anyone's interested, I have added a number of new images to illustrate this article on the French Knowledge. Best, --
104:
20:
456:
dumping this link too---it's actually a would-be program for finding Hamiltonian paths that hasn't been updated in a while
74:
1125:
213:
141:
1089:
65:
1077:
721:
1137:
1280:
1233:
1010:
974:
966:
867:
474:
1217:
849:
803:
755:
701:
675:
656:
632:
576:
352:
109:
1101:
517:
378:
448:
1065:
1045:
908:
815:
219:
716:"vertex has a full degree smaller than n." could someone can explain what does "full degree" means? --
263:
951:
934:
916:
717:
693:
190:
1276:
1253:
1229:
1006:
970:
891:
821:
597:"A tournament (with more than 2 vertices) is Hamiltonian if and only if it is strongly connected."
161:
55:
285:
on Knowledge. If you would like to participate, please visit the project page, where you can join
1257:
845:
799:
751:
671:
628:
572:
269:
70:
417:
253:
232:
1030:
875:
794:. This assumption is perfectly logical given that the term is introduced on an article titled
648:
547:
527:
51:
1061:
1041:
962:
795:
470:
396:
above stuff deleted from main page since it doesn't have much to do with Hamiltonian paths.
24:
870:
be merged into this page in a section describing in detail the problem and its complexity.
995:
947:
930:
912:
690:
Does this game fall within this article's scope? If not, is it worth a separate article?
605:
478:
444:
1194:
A Hamiltonian graph where none of the preceding theorems can be applied (Wagner's graph)
904:
743:
410:
Hamilton Icosian Calculus used to investigate closed edge paths on a dodecahedron that
1228:
incorrect for this procedure to turn a non-Hamiltonian graph into a Hamiltonian one. —
1292:
1272:
1252:
I think a start would be to expand the current article with a section on that topic.
929:
Hi, seeing as there seems to be no further discussion, shall I remove the merge tag?
498:
1026:
946:
I've removed the merge tags from both pages since there was no further discussion.
871:
564:
560:
542:
514:
457:
432:
397:
814:
I'm sure its definition could be clarified, but the term "Hamiltonian graph" is a
734:
I'm not extremely familiar with directed graphs, but do know that one can discuss
477:. Although they are related, I think it is clearer to put them on separate pages.
888:
Knowledge talk:WikiProject Computer science/Archive 8#Merging "X problem" to "X"
282:
991:
775:
618:
601:
259:
1284:
1261:
1237:
1221:
1069:
1049:
1034:
1014:
999:
978:
955:
938:
920:
879:
853:
834:
807:
759:
725:
705:
679:
660:
636:
609:
580:
549:
534:
501:
493:, 2006) call the Hamilton path the "Rudrata path" after the Kashmiri poet
356:
382:
489:
Some authors (notably, Dasgupta, Papadimitriou, & Vazirani in their
494:
374:
746:. I assume that whomever placed these theorems was using the term
1040:
If that's so easy, why not add the demonstration or a source? --
184:
15:
418:
http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/Icosian/
1267:
Should we add "Not to be confused with Eulerian path"?
1119:
Proof of Dirac's theorem (step 1) and of Ore's theorem
160:
451:
which would solve the "Hamiltonian Circuit Problem".
281:, a collaborative effort to improve the coverage of
890:, and though there was no consensus, I agree with
591:Why does this article seem to contradict itself?
594:"every has an odd number of Hamiltonian paths"
33:for general discussion of the article's subject.
1319:Knowledge level-5 vital articles in Mathematics
1182:Usage example of Bondy-Chvatal theorem (step 3)
1170:Usage example of Bondy-Chvatal theorem (step 2)
895:
616:Recommend clarification of the term Hamiltonian
174:
8:
961:I have added DAB links to the start of both
866:I'm proposing that the content on the page
227:
667:Disagree and recommend changes to wording
600:These statements do not seem to agree. --
903:and the final decision was to not merge
1309:Knowledge vital articles in Mathematics
1155:Usage example of Bondy-Chvatal theorem
1073:
229:
188:
445:Hamiltonian Circuit Experiment Program
1324:C-Class vital articles in Mathematics
7:
275:This article is within the scope of
218:It is of interest to the following
23:for discussing improvements to the
14:
1334:Mid-priority mathematics articles
1131:Proof of Dirac's theorem (step 2)
295:Knowledge:WikiProject Mathematics
1304:Knowledge level-5 vital articles
1187:
1175:
1163:
1148:
1136:
1124:
1112:
1100:
1088:
1076:
985:Computer Programming algorithms.
557:Agreed, but for different reason
343:vertex in the graph is visited!
298:Template:WikiProject Mathematics
262:
252:
231:
198:
189:
45:Click here to start a new topic.
1200:incorrect definition of closure
766:Remove term "Hamiltonian Graph"
315:This article has been rated as
1314:C-Class level-5 vital articles
1262:16:54, 25 September 2017 (UTC)
1095:Graph that is semi-hamiltonian
412:visit each vertex exactly once
1:
1143:Usage example of Posa theorem
1083:Graph that is not hamiltonian
1035:21:17, 6 September 2012 (UTC)
1021:Prism graphs are Hamilitonian
610:18:40, 22 February 2008 (UTC)
407:doesn't have much to do with?
289:and see a list of open tasks.
42:Put new text under old text.
1329:C-Class mathematics articles
1157:(this image existed already)
706:16:33, 8 November 2009 (UTC)
550:21:45, 26 October 2007 (UTC)
1070:13:17, 3 January 2013 (UTC)
1050:13:41, 3 January 2013 (UTC)
778:'s comment in the section
726:01:09, 7 January 2010 (UTC)
377:, or family of systems, of
50:New to Knowledge? Welcome!
1350:
1015:19:37, 20 March 2011 (UTC)
1000:17:54, 20 March 2011 (UTC)
979:04:24, 29 March 2011 (UTC)
956:04:54, 2 August 2010 (UTC)
780:Contradiction: tournaments
587:Contradiction: Tournaments
535:19:32, 14 April 2007 (UTC)
502:11:57, 10 April 2007 (UTC)
1244:Hamiltonian decomposition
1107:Graph that is hamiltonian
939:23:19, 16 July 2010 (UTC)
921:02:20, 20 June 2010 (UTC)
880:01:56, 20 June 2010 (UTC)
742:as discussed on the page
661:11:50, 22 July 2009 (UTC)
559:. The new image added by
481:17:58, 24 Jan 2005 (UTC)
314:
247:
226:
80:Be welcoming to newcomers
1285:22:12, 15 May 2022 (UTC)
1238:23:49, 7 June 2014 (UTC)
1222:23:37, 7 June 2014 (UTC)
967:Hamiltonian path problem
868:Hamiltonian path problem
854:07:17, 18 May 2010 (UTC)
835:01:35, 17 May 2010 (UTC)
808:01:16, 17 May 2010 (UTC)
760:01:24, 17 May 2010 (UTC)
680:01:04, 17 May 2010 (UTC)
637:00:54, 17 May 2010 (UTC)
627:is strongly connected."
581:00:42, 17 May 2010 (UTC)
475:Hamiltonian path problem
460:19:28, 11 Sep 2003 (UTC)
435:20:26, 11 Sep 2003 (UTC)
400:19:21, 11 Sep 2003 (UTC)
321:project's priority scale
357:15:39, 9 May 2017 (UTC)
278:WikiProject Mathematics
1299:C-Class vital articles
900:
75:avoid personal attacks
909:Clique (graph theory)
379:non-commutative roots
205:level-5 vital article
100:Neutral point of view
786:and the Hamiltonian
507:Better example image
338:Incorrect Definition
301:mathematics articles
105:No original research
892:User:David Eppstein
449:NP-Complete Problem
373:A conception of a
270:Mathematics portal
214:content assessment
86:dispute resolution
47:
696:comment added by
649:regular polytopes
465:Separated article
335:
334:
331:
330:
327:
326:
183:
182:
66:Assume good faith
43:
1341:
1191:
1179:
1167:
1152:
1140:
1128:
1116:
1104:
1092:
1080:
963:Hamiltonian path
833:
816:very common term
796:Hamiltonian path
774:As evidenced by
772:Confusion making
732:Unclear, I agree
708:
522:
471:Hamiltonian path
369:Icosian Calculus
303:
302:
299:
296:
293:
272:
267:
266:
256:
249:
248:
243:
235:
228:
211:
202:
201:
194:
193:
185:
179:
178:
164:
95:Article policies
25:Hamiltonian path
16:
1349:
1348:
1344:
1343:
1342:
1340:
1339:
1338:
1289:
1288:
1269:
1246:
1202:
1195:
1192:
1183:
1180:
1171:
1168:
1159:
1153:
1144:
1141:
1132:
1129:
1120:
1117:
1108:
1105:
1096:
1093:
1084:
1081:
1058:
1023:
987:
864:
862:Merger proposal
831:
819:
768:
718:Arthur MILCHIOR
714:
691:
688:
645:
643:platonic solids
589:
518:
509:
487:
467:
371:
340:
300:
297:
294:
291:
290:
268:
261:
241:
212:on Knowledge's
209:
199:
121:
116:
115:
114:
91:
61:
12:
11:
5:
1347:
1345:
1337:
1336:
1331:
1326:
1321:
1316:
1311:
1306:
1301:
1291:
1290:
1277:EditorPerson53
1268:
1265:
1245:
1242:
1241:
1240:
1230:David Eppstein
1214:123.234.83.138
1201:
1198:
1197:
1196:
1193:
1186:
1184:
1181:
1174:
1172:
1169:
1162:
1160:
1154:
1147:
1145:
1142:
1135:
1133:
1130:
1123:
1121:
1118:
1111:
1109:
1106:
1099:
1097:
1094:
1087:
1085:
1082:
1075:
1057:
1054:
1053:
1052:
1022:
1019:
1018:
1017:
1007:Thore Husfeldt
986:
983:
982:
981:
971:Rupert Clayton
944:
943:
942:
941:
924:
923:
905:Clique problem
901:
863:
860:
859:
858:
857:
856:
838:
837:
827:
822:Justin W Smith
811:
810:
767:
764:
763:
762:
744:Directed graph
713:
710:
687:
684:
683:
682:
644:
641:
640:
639:
588:
585:
584:
583:
553:
552:
538:
537:
508:
505:
486:
483:
466:
463:
462:
461:
453:
452:
441:
440:
439:
438:
437:
436:
423:
422:
421:
420:
415:
408:
402:
401:
393:
392:
390:
370:
367:
363:
361:
346:
339:
336:
333:
332:
329:
328:
325:
324:
313:
307:
306:
304:
287:the discussion
274:
273:
257:
245:
244:
236:
224:
223:
217:
195:
181:
180:
118:
117:
113:
112:
107:
102:
93:
92:
90:
89:
82:
77:
68:
62:
60:
59:
48:
39:
38:
35:
34:
28:
13:
10:
9:
6:
4:
3:
2:
1346:
1335:
1332:
1330:
1327:
1325:
1322:
1320:
1317:
1315:
1312:
1310:
1307:
1305:
1302:
1300:
1297:
1296:
1294:
1287:
1286:
1282:
1278:
1274:
1273:Eulerian path
1266:
1264:
1263:
1259:
1255:
1250:
1243:
1239:
1235:
1231:
1226:
1225:
1224:
1223:
1219:
1215:
1211:
1208:
1199:
1190:
1185:
1178:
1173:
1166:
1161:
1158:
1151:
1146:
1139:
1134:
1127:
1122:
1115:
1110:
1103:
1098:
1091:
1086:
1079:
1074:
1072:
1071:
1067:
1063:
1055:
1051:
1047:
1043:
1039:
1038:
1037:
1036:
1032:
1028:
1020:
1016:
1012:
1008:
1004:
1003:
1002:
1001:
997:
993:
984:
980:
976:
972:
968:
964:
960:
959:
958:
957:
953:
949:
940:
936:
932:
928:
927:
926:
925:
922:
918:
914:
910:
906:
902:
899:
893:
889:
884:
883:
882:
881:
877:
873:
869:
861:
855:
851:
847:
846:Clifsportland
842:
841:
840:
839:
836:
832:
830:
824:
823:
817:
813:
812:
809:
805:
801:
800:Clifsportland
797:
793:
789:
785:
781:
777:
773:
770:
769:
765:
761:
757:
753:
752:Clifsportland
749:
745:
741:
737:
733:
730:
729:
728:
727:
723:
719:
711:
709:
707:
703:
699:
695:
685:
681:
677:
673:
672:Clifsportland
668:
665:
664:
663:
662:
658:
654:
650:
642:
638:
634:
630:
629:Clifsportland
625:
620:
617:
614:
613:
612:
611:
607:
603:
598:
595:
592:
586:
582:
578:
574:
573:Clifsportland
570:
566:
562:
558:
555:
554:
551:
548:
546:
545:
540:
539:
536:
533:
532:
530:
525:
524:
521:
516:
511:
510:
506:
504:
503:
500:
496:
492:
484:
482:
480:
476:
472:
464:
459:
455:
454:
450:
446:
443:
442:
434:
429:
428:
427:
426:
425:
424:
419:
416:
413:
409:
406:
405:
404:
403:
399:
395:
394:
391:
389:
388:
387:
384:
381:of unity for
380:
376:
368:
366:
362:
359:
358:
354:
350:
344:
337:
322:
318:
312:
309:
308:
305:
288:
284:
280:
279:
271:
265:
260:
258:
255:
251:
250:
246:
240:
237:
234:
230:
225:
221:
215:
207:
206:
196:
192:
187:
186:
177:
173:
170:
167:
163:
159:
155:
152:
149:
146:
143:
140:
137:
134:
131:
127:
124:
123:Find sources:
120:
119:
111:
110:Verifiability
108:
106:
103:
101:
98:
97:
96:
87:
83:
81:
78:
76:
72:
69:
67:
64:
63:
57:
53:
52:Learn to edit
49:
46:
41:
40:
37:
36:
32:
26:
22:
18:
17:
1270:
1251:
1247:
1212:
1206:
1203:
1156:
1059:
1024:
988:
945:
896:
865:
825:
820:
791:
787:
783:
779:
771:
747:
739:
735:
731:
715:
698:72.72.49.169
689:
686:Numbrix game
666:
653:85.166.68.45
646:
623:
615:
599:
596:
593:
590:
568:
556:
543:
531:
528:
523:
519:
490:
488:
485:Rudrata path
469:I separated
468:
411:
372:
364:
360:
349:79.66.220.18
345:
341:
317:Mid-priority
316:
276:
242:Mid‑priority
220:WikiProjects
203:
171:
165:
157:
150:
144:
138:
132:
122:
94:
19:This is the
1062:MathsPoetry
1042:MathsPoetry
748:full degree
712:Full degree
692:—Preceding
383:geometrical
292:Mathematics
283:mathematics
239:Mathematics
148:free images
31:not a forum
1293:Categories
1056:New images
948:Shreevatsa
931:Shreevatsa
913:Shreevatsa
872:-- Aronzak
491:Algorithms
479:MathMartin
740:outdegree
208:is rated
88:if needed
71:Be polite
21:talk page
1254:Hardmath
736:indegree
694:unsigned
56:get help
29:This is
27:article.
1027:myncknm
788:circuit
561:Arthena
544:Arthena
495:Rudrata
458:Populus
433:Populus
398:Populus
319:on the
210:C-class
154:WPÂ refs
142:scholar
1207:adding
565:Charon
515:Charon
375:system
216:scale.
126:Google
992:Cliff
907:with
829:stalk
776:AlanH
619:AlanH
602:AlanH
197:This
169:JSTOR
130:books
84:Seek
1281:talk
1258:talk
1234:talk
1218:talk
1066:talk
1046:talk
1031:talk
1011:talk
996:talk
975:talk
965:and
952:talk
935:talk
917:talk
876:talk
850:talk
804:talk
792:path
784:path
756:talk
738:and
722:talk
702:talk
676:talk
657:talk
633:talk
606:talk
577:talk
529:talk
473:and
353:talk
162:FENS
136:news
73:and
1271:An
651:?
569:not
499:Gdr
311:Mid
176:TWL
1295::
1283:)
1260:)
1236:)
1220:)
1068:)
1048:)
1033:)
1013:)
998:)
977:)
954:)
937:)
919:)
911:.
894::
878:)
852:)
806:)
758:)
724:)
704:)
678:)
659:)
635:)
624:or
608:)
579:)
355:)
156:)
54:;
1279:(
1256:(
1232:(
1216:(
1064:(
1044:(
1029:(
1009:(
994:(
973:(
950:(
933:(
915:(
874:(
848:(
826:/
802:(
754:(
720:(
700:(
674:(
655:(
631:(
604:(
575:(
526:/
520:X
414:.
351:(
323:.
222::
172:·
166:·
158:·
151:·
145:·
139:·
133:·
128:(
58:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
