Talk:Hamiltonian path

This is the talk page for discussing improvements to the Hamiltonian path article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Incorrect Definition[edit]

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).

Icosian Calculus[edit]

A conception of a system, or family of systems, of non-commutative roots of unity for geometrical 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 that visit each vertex exactly once.

http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/Icosian/

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 the NP-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 while Populus 19:28, 11 Sep 2003 (UTC)

Separated article[edit]

I separated Hamiltonian path and Hamiltonian path problem. Although they are related, I think it is clearer to put them on separate pages. MathMartin 17:58, 24 Jan 2005 (UTC)

Rudrata path[edit]

Some authors (notably, Dasgupta, Papadimitriou, & Vazirani in their Algorithms, 2006) call the Hamilton path the "Rudrata path" after the Kashmiri poet Rudrata 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. Gdr 11:57, 10 April 2007 (UTC)[reply]

Better example image[edit]

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. Charon X/talk 19:32, 14 April 2007 (UTC)[reply]

I added an example I found on the German Wikipedia article. Maybe the other one should be removed, it seems somewhat hard to follow. Arthena^(talk) 21:45, 26 October 2007 (UTC)[reply]

Agreed, but for different reason. The new image added by Arthena is a good example of a Hamiltonian Circuit, but there is no image of a non-circuitous Hamiltonian path. The orignal image that Charon 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 not 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]

Contradiction: Tournaments[edit]

Why does this article seem to contradict itself?

"every [[tournament] has an odd number of Hamiltonian paths"

"A tournament (with more than 2 vertices) is Hamiltonian if and only if it is strongly connected."

These statements do not seem to agree. --AlanH (talk) 18:40, 22 February 2008 (UTC)[reply]

Recommend clarification of the term Hamiltonian AlanH 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 or 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]

platonic solids[edit]

"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 regular polytopes? 85.166.68.45 (talk) 11:50, 22 July 2009 (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]

Numbrix game[edit]

Does this game fall within this article's scope? If not, is it worth a separate article? —Preceding unsigned comment added by 72.72.49.169 (talk) 16:33, 8 November 2009 (UTC)[reply]

Full degree[edit]

"vertex has a full degree smaller than n." could someone can explain what does "full degree" means? --Arthur MILCHIOR (talk) 01:09, 7 January 2010 (UTC)[reply]

Unclear, I agree I'm not extremely familiar with directed graphs, but do know that one can discuss indegree and outdegree as discussed on the page Directed graph. I assume that whomever placed these theorems was using the term full 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]

Remove term "Hamiltonian Graph"[edit]

Confusion making As evidenced by AlanH's comment in the section Contradiction: tournaments, the use of the term "Hamiltonian Graph" is misleading and confusing. Because this page introduces two distinct but similar ideas, the Hamiltonian path and the Hamiltonian circuit, 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 path. This assumption is perfectly logical given that the term is introduced on an article titled Hamiltonian 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 a very 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 Smith ^talk/_stalk 01: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]

Merger proposal[edit]

I'm proposing that the content on the page Hamiltonian path problem be merged into this page in a section describing in detail the problem and its complexity. -- Aronzak (talk) 01:56, 20 June 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 at Wikipedia talk:WikiProject Computer science/Archive 8#Merging "X problem" to "X", and though there was no consensus, I agree with User: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

and the final decision was to not merge Clique problem with Clique (graph theory). Shreevatsa (talk) 02:20, 20 June 2010 (UTC)[reply]

Hi, seeing as there seems to be no further discussion, shall I remove the merge tag? Shreevatsa (talk) 23:19, 16 July 2010 (UTC)[reply]

I've removed the merge tags from both pages since there was no further discussion. Shreevatsa (talk) 04:54, 2 August 2010 (UTC)[reply]

I have added DAB links to the start of both Hamiltonian path and Hamiltonian path problem 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. Rupert Clayton (talk) 04:24, 29 March 2011 (UTC)[reply]

Computer Programming algorithms.[edit]

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]

Prism graphs are Hamilitonian[edit]

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]

If that's so easy, why not add the demonstration or a source? --MathsPoetry (talk) 13:41, 3 January 2013 (UTC)[reply]

New images[edit]

In case anyone's interested, I have added a number of new images to illustrate this article on the French Wikipedia. Best, --MathsPoetry (talk) 13:17, 3 January 2013 (UTC)[reply]

Graph that is not hamiltonian
Graph that is semi-hamiltonian
Graph that is hamiltonian
Proof of Dirac's theorem (step 1) and of Ore's theorem
Proof of Dirac's theorem (step 2)
Usage example of Posa theorem
Usage example of Bondy-Chvatal theorem (this image existed already)
Usage example of Bondy-Chvatal theorem (step 2)
Usage example of Bondy-Chvatal theorem (step 3)
A Hamiltonian graph where none of the preceding theorems can be applied (Wagner's graph)

incorrect definition of closure[edit]

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 adding 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.

123.234.83.138 (talk) 23:37, 7 June 2014 (UTC)[reply]

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]

Hamiltonian decomposition[edit]

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.

I think a start would be to expand the current article with a section on that topic. Hardmath (talk) 16:54, 25 September 2017 (UTC)[reply]

Should we add "Not to be confused with Eulerian path"?[edit]

An Eulerian 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]