Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hamiltonian-path]

A path in a graph that visits each vertex exactly once.

2
votes
0answers
282 views

Greatest number of edges in a graph not containing a hamilton path

Inspired by the question, where the greatest number of edges in a hamiltonian graph was asked, I have a similar question, but for hamilton paths. How many edges can a simple undirected graph contain,...
13
votes
1answer
362 views

Who has a winning strategy in the hamilton-circle-game?

The game starts with a graph with $n$ vertices and no edges. The players alternately add edges until the graph contains a hamilton-circle. The player who made the last move loses. Who has a winning ...
1
vote
0answers
160 views

Conditions for a $2$-connected graph to be hamiltonian?

Let G be a simple undirected graph. If G is connected, and every vertex has degree $2$, then G is hamiltonian. (In fact, G only consists of the hamilton-circle) Are there some weaker sufficient ...
9
votes
1answer
727 views

What is the maximum number of edges in an $n$-vertex non-Hamiltonian graph of minimum degree at least $2$?

Q: What is the maximum number of edges in an $n$-vertex non-Hamiltonian (simple) graph of minimum degree at least $2$? This question relates to Maximum number of edges in a non-Hamiltonian graph ...
9
votes
0answers
113 views

How many hamilton paths can a non-hamiltonian graph have?

What is the maximum number of hamilton paths a graph with $n$ vertices can have without having a hamiton cycle ? If my turbo pascal program works well, the first few values for $3,4,...$ vertices ...
7
votes
1answer
163 views

Is there a name for graphs with the following property?

The property of the graph is the following: For any vertex, there is a hamiltonian path starting with this vertex, but the graph is not hamiltonian. The following graph is a small example: Important ...
6
votes
1answer
1k views

Proof that there is no closed knight tour on a $3\ \times\ 8$ - board

I want to prove that there is no closed knight tour on a $3\ \times\ 8$ - board by deleting $s$ vertices of the corresponding knight graph to get a graph with more than $s$ connected components (...
4
votes
3answers
19k views

Proving Hamiltonian Cycle is NP Complete

I'm trying to learn Complexity classes.I want to show Hamiltonian cycle is NP Complete. The text tells me that Inorder to prove NP-Completeness we first show it belongs to NP,by taking a certificate....
3
votes
0answers
132 views

Studying Hamiltonian PDEs - Where to start?

I first got in contact with Hamiltonian PDEs when I wrote my first thesis about the Nash-Moser-Theorem as some books mentioned them as a field of application of this theorem. As those examples were ...
0
votes
1answer
79 views

Hamiltonian cycle adjacency sum Proof

Let $C$ be a Hamiltonian cycle on a graph with vertices labeled {$1,...,9$}. Prove that there are $3$ vertices adjacent in $C$ whose labels sum to at least $12$. I understand why this fact is true by ...
2
votes
3answers
7k views

Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.

In a complete graph with $n$ vertices there are $\frac{n−1}{2}$ edge-disjoint Hamiltonian cycles if $n$ is an odd number and $n\ge 3$. What if $n$ is an even number?
1
vote
1answer
767 views

Hamiltonian paths in bipartite graphs

Is there a way to find the exact number of Hamiltonian paths in special cases of bipartite graphs, for example, the K(n,n) complete bipartite graph for n ≥ 3? Thanks.
2
votes
0answers
81 views

Hamiltonian form of PDE

I am quite new in this field and I was wondering what does exactly mean to write a PDE (in 2 or 3 dimensions) in an Hamiltonian form. More in detail, is there any standard procedure to write a given ...
2
votes
1answer
43 views

Making a graph Hamiltonian by stacking it up

Consider a graph $G$. As usual, denote a path graph of length $n$ as $P_{n}$, and $\times$ is for Cartesian product of graph. If $G$ is Hamiltonian (ie. have a Hamiltonian cycle) then it is easy to ...
3
votes
0answers
128 views

Is there away to swap adjacent items in a sequence, such that each permutation occurs once?

Let's us say you have a finite sequence of things. Some are identical, some distinct. For example: $$\langle 2,5,7,2,3\rangle$$ Now, under what conditions can each permutation of a sequence be ...
8
votes
1answer
682 views

Does every connected $r$-regular bipartite graph contain a Hamiltonian cycle?

Here's a quickie: Let $r\ge2$. Does every connected $r$-regular bipartite graph contain a Hamiltonian cycle? I've been playing around with this for almost an hour, but I can't prove it.
2
votes
0answers
90 views

Generalized-knight's tour

Define an $(a,b)$-knight as a chess piece that moves $a$ squares horizontally and $b$ squares vertically, or vice versa, in either order. Thus a normal chess knight is a $(1,2)$-knight. For which $...
0
votes
2answers
588 views

Prove a consequence of Ore's Theorem in Graph theory.

Let $G$ be a graph of degree $n\ge 3$ that satisfies the requirements of Ore's Theorem (my professor refers to it as "Ore's Condition"), to prove that $G+a$, $a$ an edge also satisfies Ore's Theorem. (...
1
vote
1answer
251 views

Eulerian path for Rubik's Cube states

There are a number of discussions online confirming that there exists a Hamiltonian cycle through the states of a Rubik's Cube. Or more precisely, the "quarter-turn metric Cayley graph for the Rubik's ...
1
vote
2answers
2k views

Hamilton Paths in n-Wheel Graph

According to wolfram, $n$-wheel graphs have $4(n-1)(n-2)$ Hamilton paths in them. $n$-wheel graph = http://mathworld.wolfram.com/WheelGraph.html http://mathworld.wolfram.com/HamiltonianPath.html ...
0
votes
1answer
69 views

Why is G a cycle? Graph G with n vertices, m edges. “(∀v ∈ V(G) : δ(v) = 2 ⇒ G is Hamiltonian) is true because G is a cycle”.

I'm reviewing an earlier exam with solutions by the professor. I found this: Problem: Let G denote a simple, connected graph with n vertices and m edges. Translate the following statement to ...
8
votes
2answers
242 views

Chance of Hamiltonian Path in Sudoku cell

Checking the correctness of a daily Sudoku I'd just finished, I noticed a curious pattern in one of the 3x3 cells: 1 9 3 8 2 4 7 6 5 Note that each of the ...
3
votes
1answer
2k views

Transitive tournament

1.) Prove that a tournament (i.e., an orientation of $K_n$) is a transitive tournament if and only if it does not have any directed cycles of length $3$. 2.) Prove that a tournament is strongly ...
5
votes
1answer
311 views

Probability of finding a Hamilton circuit in a graph

In short, I would like to know either/both the probability that there exists a Hamiltonian circuit within a graph, or the number of circuits expected to exist. (Without actually finding all the ...
2
votes
1answer
185 views

Prove 2-HamiltonianCycle $\in \textbf{NP}$

Just want to verify that I have the right idea here with this hamiltonian cycle question. $HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex ...
0
votes
2answers
846 views

Hamilton Graph and Complete Tripartite

1) Consider the complete tripartite graph $K_2,_3,_n$ for $n \ge 3$. Determine for what values of n the graph $K_2,_3,_n$ has a Hamilton path, and for what values of n the graph has a Hamilton cycle. ...
1
vote
1answer
137 views

Show that cubic hamiltonian graph is edge-3-colourable.

How can I show that cubic hamiltonian graph is edge-3-colourable?
2
votes
1answer
604 views

Alternative proof of 'a linegraph of a Hamiltonian graph is Hamiltonian'?

So I've got an assignment to proof that the linegraph of a normal Hamiltonian graph is also Hamiltonian (but not Eulerian most of the time). I've found that this is a direct corollary of a theorem of ...
4
votes
3answers
1k views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
2
votes
2answers
7k views

Connected graph - 5 vertices eulerian not hamiltonian

i need to give an example of a connected graph with at least 5 vertices that has as an Eulerian circuit, but no Hamiltonian cycle?
0
votes
0answers
252 views

traversing faces of a polyhedron Hamiltonian Tour?

I wanted to know if I could start at one point on an icosahedron and traverse to all the others sequentially without visiting any one twice, which I assume I could model as a Hamiltonian path in a ...
0
votes
1answer
67 views

Adding a point to shortest path

If there exists a set of n points in a 2D coordinate system and an n-dimensional vector V ...
1
vote
1answer
458 views

Hamiltonian paths in cubic graph

Prove, that in cubic graph, for given vertices $u$ and $v$, there are even number of Hamiltonian paths which connect $u$ and $v$. I got a hint, that considering a "metagraph", where vertices are ...
2
votes
2answers
924 views

Clarifying Dirac's theorem

Theorem : If $G$ is a simple graph with $n$ vertices with $ n ≥ 3$ such that the degree of every vertex in G is at least $ n/2$, then $G$ has a Hamilton circuit. In this if $n$ is odd, should I ...
6
votes
1answer
495 views

Homework - Proof: Is this particular graph Hamiltonian?

I have a homework for my class to Combinatorics and Graphs which I'm not sure how to finish. The task: Let G be a simple graph on 14 vertices, with 4 vertices having degree 5 and 10 vertices having ...
0
votes
2answers
431 views

Euler & Hamiltonian Cycles

How would one illustrate a graph that has both an Euler cycle and a Hamiltonian cycle, but they are not the same? From what I read, the Euler cycles themselves must have included edges and vertices, ...
3
votes
1answer
5k views

Number of Hamiltonian Paths on a (in)complete graph

This question is motivated by a problem on a local programming competition (you can find the original problem statement here: http://maratona.algartelecom.com.br/files/12maratona.zip , problem E on ...
3
votes
1answer
877 views

Proof: Gradient of a Hamiltonian System

I am trying to prove the following: Given that $f \in C^1(E) $ where E is a open simply connected subsets of the plane. Show that the system $\dot x=f(x)$ is a hamiltonian if and only if $\nabla \...
0
votes
1answer
165 views

Question on hamiltonian graph

Can anyone give me an example of a Hamiltonian graph $H$ of order $n=2k$ for some $k\geq 2$ where $k$ vertices have degree $2$, no two vertices of which are adjacent, while the remaining vertices have ...
1
vote
0answers
201 views

Complete tripartite graph hamiltonian

Let $G_{a,b,c}$ be a complete tripartite graph. For what values of $a, b$ and $c$ is $G_{a,b,c}$ Hamiltonian?
1
vote
2answers
3k views

Graph Theory: How do we know Hamiltonian Path exists in graph where every vertex has degree ≥3?

I am trying to prove that if every node of a graph G has degree of at least 3 then G contains a cycle and a chord. My current approach is as follows: Separate the graph G into connected components ...
1
vote
0answers
413 views

Are there necessary and sufficient conditions of a graph to decompose into two Hamiltonian cycles?

Let $G$ be a graph. Definition: $G$ is decomposable into two Hamiltonian cycles if the edge set $E(G)$ can be partitioned into two disjoint Hamiltonian cycles. Obviously, if $G$ is decomposable into ...
5
votes
4answers
5k views

Maximum number of edges in a non-Hamiltonian graph

I need to show that the maximum number of edges of non-Hamiltonian, simple graph, on $n$ vertices noted by $t(n,H_n)$ is $\binom{n-1}{2} + 1$. It's essential to show the upper and lower bounds for ...
6
votes
3answers
4k views

Proving that a graph of a certain size is Hamiltonian

For any graph with order $n \geq 3$, given that its size is $$m \geq \frac{\left(n-1\right)(n-2)}{2} + 2,$$ show that the graph is Hamiltonian. I know that if I can show that the degree sum of any ...
20
votes
3answers
6k views

How many knight's tours are there?

The knight's tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight's move. Tours can be cyclic, ...