This is thetalk page for discussing improvements to theHamiltonian path article. This isnot a forum for general discussion of the subject of the article.
This article is within the scope ofWikiProject Mathematics, a collaborative effort to improve the coverage ofmathematics on Wikipedia. If you would like to participate, please visit the project page, where you can jointhe discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
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* vertex in the graph is visited!
-- 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!79.66.220.18 (talk)15:39, 9 May 2017 (UTC)[reply]
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).
A conception of asystem, or family of systems, ofnon-commutative roots of unity forgeometrical 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.
[to be finished;]
[solutions of hamilitonian circuits]
above stuff deleted from main page since it doesn't have much to do with Hamiltonian paths.Populus 19:21, 11 Sep 2003 (UTC)
doesn't have much to do with?
Hamilton Icosian Calculus used to investigate closed edge paths on a dodecahedron thatvisit each vertex exactly once.
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.Populus 20:26, 11 Sep 2003 (UTC)
Hamiltonian Circuit Experiment Program - Offer prize of one million dollars promised to those who solve the seven problems unsolved at the end of 20th century, one being theNP-Complete Problem which would solve the "Hamiltonian Circuit Problem".
dumping this link too---it's actually a would-be program for finding Hamiltonian paths that hasn't been updated in a whilePopulus 19:28, 11 Sep 2003 (UTC)
Some authors (notably, Dasgupta, Papadimitriou, & Vazirani in theirAlgorithms, 2006) call the Hamilton path the "Rudrata path" after the Kashmiri poetRudrata 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.Gdr11:57, 10 April 2007 (UTC)[reply]
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.CharonX/talk19:32, 14 April 2007 (UTC)[reply]
Agreed, but for different reason. The new image added byArthena is a good example of a Hamiltonian Circuit, but there is no image of a non-circuitous Hamiltonian path. The orignal image thatCharon 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 doesnot 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.Clifsportland (talk)00:42, 17 May 2010 (UTC)[reply]
Isn't there or shouldn't there be some minimum standard for figure legends? For the figure of the three graphs, not one aspect of the graph is mentioned in the legend. (vertices? curcuits?)It is completely incomprehensible as is. You have to know what you should see, to see it. It is the equivalent of showing a picture of the night sky and a legend that says "supernovae".True, but unhelpful. When you decide on a figure make a legend to go with .~2025-42966-49 (talk)17:06, 25 December 2025 (UTC)[reply]
Recommend clarification of the term HamiltonianAlanH 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. Circuitor 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 is strongly connected."Clifsportland (talk)00:54, 17 May 2010 (UTC)[reply]
Disagree and recommend changes to wording 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 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."Clifsportland (talk)01:04, 17 May 2010 (UTC)[reply]
Unclear, I agree I'm not extremely familiar with directed graphs, but do know that one can discussindegree andoutdegree as discussed on the pageDirected graph. I assume that whomever placed these theorems was using the termfull degree 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.Clifsportland (talk)01:24, 17 May 2010 (UTC)[reply]
Confusion making As evidenced byAlanH's comment in the sectionContradiction: tournaments, the use of the term "Hamiltonian Graph" is misleading and confusing. Because this page introduces two distinct but similar ideas, the Hamiltonianpath and the Hamiltoniancircuit, 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 Hamiltonianpath. This assumption is perfectly logical given that the term is introduced on an article titledHamiltonian path. 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".Clifsportland (talk)01:16, 17 May 2010 (UTC)[reply]
I'm sure its definition could be clarified, but the term "Hamiltonian graph" is avery common term, 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.Justin W Smithtalk/stalk01:35, 17 May 2010 (UTC)[reply]
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.Clifsportland (talk)07:17, 18 May 2010 (UTC)[reply]
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 atWikipedia talk:WikiProject Computer science/Archive 8#Merging "X problem" to "X", and though there was no consensus, I agree withUser:David Eppstein:
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 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
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.Cliff (talk)17:54, 20 March 2011 (UTC)[reply]
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.Thore Husfeldt (talk)19:37, 20 March 2011 (UTC)[reply]
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.myncknm (talk)21:17, 6 September 2012 (UTC)[reply]
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 byadding 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.
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 incorrect for this procedure to turn a non-Hamiltonian graph into a Hamiltonian one. —David Eppstein (talk)23:49, 7 June 2014 (UTC)[reply]
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 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 Wikipedia article, yet.
AnEulerian path 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.EditorPerson53 (talk)22:12, 15 May 2022 (UTC)[reply]
level-5 vital article is ratedC-class on Wikipedia'scontent assessment scale.
