Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
35 views

What is a vertex-transitive graph? (Question about Lovász Conjecture)

I was reading about Lovász Conjecture and came across the following definition on Wikipedia of a vertex-transitive graph (see below). $\bullet$ It states that a graph is vertex-transitive if for any ...
0
votes
1answer
46 views

Hamiltonian circuit

Prove that a graph that posses a Hamiltonian circuit must have no pendant vertices. To prove this, each vertex in a graph, that also has a hamiltonian circuit, much acquire at least two edges in ...
0
votes
0answers
25 views

Hamiltonian paths and cycles of rook graph on $n\times2$ chessboard

According to OEIS, there are closed form for directed Hamiltonian paths (A096121) and Hamiltonian cycles (A276356) of rook graph on $n\times2$ chessboard. Are there papers which include proof of those ...
1
vote
1answer
35 views

Number of different graphs with this degree sequence

The set of degree sequences in question is: $$ D_1=\{4^4,6^4,4^4\} $$ $$ D_2=\{4^4,6^4,6^4,4^4\} $$ $$ D_3=\{4^4,6^4,6^4,6^4,4^4\} $$ $$ D_4=\{4^4,6^4,6^4,6^4,6^4,4^4\} $$ $$ ... $$ $$ D_N=\{4^4,...
2
votes
0answers
16 views

Path / Graph problem with X nodes looking for Y paths with the most similar length.

I have the following graph / path problem: There is exactly 1 start node and 1 end node. There are also X (in this case 7) nodes, each connected to all other nodes and the start and end node with ...
1
vote
1answer
23 views

Graph Problem: find X path lengths which are closest to each other (similar to shortest path)

I have the following problem: 1 Start point 1 End point 7 Knots / waypoints which you have to visit in any order All 9 knots are connected with each other. All paths have to start at the start point ...
0
votes
0answers
45 views

is it possible to move a knight on a chessboard such that it completes every permissible move exactly once?

a move between two squares is counted as one regardless of the direction. basically, we want to prove that a knight started from any position in a 8*8 chessboard can go to all the possible places in ...
2
votes
1answer
39 views

What is the term for a graph in which each edge belongs to a Hamiltonian cycle?

Furthermore, are they any known results about these graphs, such as necessary or sufficient conditions for a graph to have this property?
0
votes
2answers
108 views

About the proof of a graph is not Hamiltonian.

Given the following graph: https://i.stack.imgur.com/fg2Q9.png Is this graph Hamiltonian or not? The answer is no. What I tried to prove is by using the fact that: "if a vertex in the graph has ...
1
vote
1answer
62 views

Show that if $|G| \geq 5$ and for each pair of vertices $u,v$ there is an $u−v$ Hamilton path then $\kappa(G) \geq 3$

Show that if $G$ is a graph with $|G| \geq 5$ such that for each pair of vertices $u,v$ there is an $u−v$ Hamilton path in $G$, then $\kappa(G) \geq 3$ I do not really have any idea how to start this ...
2
votes
2answers
87 views

Prove that if a graph $G$ has a Hamilton path, then for every $S\subseteq V(G)$, the number of components of $G-S$ is at most $|S|+1$.

Prove that if a graph $G$ has a Hamilton path, then for every $S\subseteq V(G)$, the number of components of $G-S$ is at most $|S|+1$. My solution (rough and incorrect): Consider a Hamilton path $P$ ...
2
votes
0answers
24 views

Number of open and closed rook's tours

Knight's tour is very well known problem, but what about rook's tour? On $n\times1$ chessboard there are obviously $n!$ open and $(n-1)!$ closed tours. Is there a way to easily compute number of open ...
1
vote
0answers
37 views

Hamiltonian paths in graph

I have a theorem about Hamiltonian paths in graph, but I doubt it's possible. Theorem If vertex $v$ of graph $G$ is not isolated, and degree of every other vertex is $\geq k$ for $k \geq 2$, and $|V| ...
0
votes
1answer
119 views

Every self-complementary graph contains a Hamiltonian path.

How to show that every self-complementary graph is traceable (contains a Hamiltonian path)? Definitions: Self-complementary graph Hamiltonian-Path Traceable Graph
0
votes
1answer
40 views

Diameter of a graph such that given independent vertices u, v, d(u) + d(v) ≥ n.

given my continuous struggle with proofs on graph theory, I come with another problem I do not know how to approach. Given a graph G = (V, E) such that for any two non-neighboring vertices u, v ∈ V ,...
2
votes
0answers
78 views

Is this graph Hamiltonian and how to prove it is not? [closed]

How to prove this graph is not Hamiltonian (does not contain a Hamiltonian cycle)? I have already tried removing some vertices from the graph, but I cannot get more than 7 connected components after ...
0
votes
0answers
20 views

Hamiltonian cycles and paths in a graph

I want to present you a lemma, that I've almost proved, but i'm stuck at the very end of it. Lemma If vertex $v$ of a graph $G$ is not isolated and degree of every vertex except $v$ is $\geq k$ (for $...
8
votes
1answer
338 views

All 4-connected planar graphs are Hamiltonian-connected

I started reading Thomassen's paper A Theorem on Paths in Planar Graphs, where he proves one of Plummer's conjectures: Every $4$-connected planar graph is Hamiltonian-connected. Context. Recall that ...
0
votes
1answer
72 views

Hamilton Paths in Complete graph $K_n$

In complete graph $K_n$, is it true that we can have at least $2*n$ Hamilton paths?
0
votes
1answer
33 views

Hamilton path and Euler circuits in Cycle graph

Can $C_n$ has $2*n$ Euler circuits and $3*n$ Hamilton paths in the Cyclic graphs?
0
votes
0answers
33 views

A Hamilton graph having a Hamilton cycle that traverse an edge more than once.

I was asked to draw a Hamilton graph having a Hamilton cycle that traverse an edge more than once. My first impression of this question was: what? I mean if we are not allowed to visit a vertex more ...
0
votes
1answer
81 views

Is there a non-planar, non-hamiltonian and eulerian graph?

I'm trying to find a graph that is non-planar, non-hamiltonian and eulerian but I can't find anyone. Is this possible? Thanks
2
votes
1answer
124 views

How to show that complement a of regular graph is a Hamiltonian graph? [closed]

I have a regular graph G of degree k ≥ 1 (ie its every vertex is of degree k) with at least 2k+2 vertices. How do I show that complement of G is a Hamiltonian graph?
0
votes
1answer
135 views

How many Hamiltonian cycles in a complete graph cover edges that don't share vertices?

Consider a complete graph, K, that has n vertices. There is a set of edges within K that have a common property, which is that they do not share vertices anywhere on the graph. Let's call these set ...
0
votes
1answer
259 views

How many Hamiltonian cycles are there in a complete graph that must contain certain edges?

Consider a complete graph $G$ that has $n \geq 4$ vertices. Each vertex in this graph is indexed $[n]=\{1,2,3, \dots n\}$ In this context, a Hamiltonian cycle is defined solely by the collection of ...
1
vote
2answers
255 views

How many Hamiltonian cycles are there in a complete graph if we discount the cycle's orientation or starting point?

Consider a complete graph G with n vertices. Each vertex is indexed by [n] = {1,2,3...n} where n >= 4. In this case, a Hamiltonian cycle is determined only by the collection of edges it contains, ...
2
votes
1answer
53 views

Hamiltonian paths in a simple graph

If a simple graph $G$ with $n$ vertices has a Hamiltonian cycle, what can we say about the number of Hamiltonian paths that $G$ has? Since Hamiltonian cycle goes through each vertex only once the ...
0
votes
1answer
269 views

There exists a graph on $n$ vertices such that every vertex has degree at least $\frac{1}{2}n -1$

Show that for every $n \geq 1$ there exists a graph on $n$ vertices such that every vertex has degree at least $\frac{1}{2}n -1$ and G is not Hamiltonian. I know that Dirac's theorem implies every ...
2
votes
1answer
200 views

Hamiltonian Knight's (closed) walk for odd $\times$ odd chess board

I am taking a course on graph theory right now and we were posed the following question: Show that if $n$ is odd, a knight on an $n \times n$ chessboard can not make a closed tour of the chessboard ...
0
votes
1answer
327 views

Number of Hamiltonian cycles in complete graph Kn with constraints

I am currently working on a exercice which aims to count the number of hamiltonian cycles in a complete graph. Since it is a completely new topic to me, I struggle to think about how to solve the ...
0
votes
0answers
43 views

Difference between hamiltonian and pre-hamiltonian path?

What is the difference between a hamiltonian path and a pre-hamiltonian path? Or it is the same? How do I show that a digraph G contains a pre-hamiltonian path?
1
vote
1answer
50 views

Need prove a Graphs with n >= 5 with a Euler path and without Hamilton Path and Hamilton Cycle exist.

I already proved a Euler Tour can't exist because all degrees would have to equal a number divisible by 2 but a Euler Path requires two odd degrees. I still have to prove a graph exists that contains ...
0
votes
0answers
12 views

Pseudo hamiltonian connected property of a graph

Is there a connection between pseudo hamiltonian connectedness and hamiltonicity of graphs?
3
votes
1answer
36 views

Prove a lower limit of $|E(G)|$ where for any $u,v\in G$, there exists a Hamilton path

Define a "Hamilton-connected graph $G$" as For any vertices $u, v \in G$, a Hamilton path exists, where the two ends of the path are vertices $u$ and $v$. Try to prove that if $G$ is a Hamilton-...
1
vote
1answer
95 views

$G$ has a Hamiltonian path iff $G+v$ has a Hamiltonian cycle

If $G = (V, E)$ is a simple graph with at least one vertex and $G'$ is the graph formed by adding a new vertex $v$ and making it adjacent to every vertex in $V$. How do you show that $G$ has a ...
2
votes
2answers
103 views

Where is the proof of Tutte's graph having no Hamiltonian cycles?

Tutte's graph was/is a famous counterexample to Tait's conjecture that every cubic, polyhedral graph has a Hamiltonian cycle. However, I cannot get access to Tutte's original paper (it's stuck behind ...
6
votes
0answers
110 views

The number of Hamiltonian paths in a tournament is always odd?

A tournament is defined as an orientation of a complete graph. Prove or disprove the following statement: In a tournament, there are exactly an odd number of Hamiltonian paths. In all cases I’ve ...
0
votes
1answer
141 views

if G does not have vertices of odd degree, then there are disjoints cycles by edges

Show that if G does not have vertices of odd degree, then there are disjoints cycles by edges $C_{1}, C_{2}, C_{3},...C_{m}$ such that $E(G)=E(C_{1}) \cup E(C_{2})\cup ...\cup...\cup E(C_{M})$ I ...
1
vote
0answers
22 views

Is there a Hamiltonian path? (i.e. can the general associative law be solved with Graph Theory?) [duplicate]

Consider the different bracketings of the summation $$1+2+3+4+5\,.$$ I've listed them all below: $$ 1+(2+(3+(4+5)))\,,\quad (1+((2+3)+4))+5\\ 1+(2+((3+4)+5))\,,\quad (1+(2+(3+4)))+5\\ 1+((2+(3+4))+...
2
votes
0answers
120 views

Doubt on the definition of closure of a graph.

The closure of a graph $G$, denoted $cl(G)$ is defined to be the supergraph of $G$ obtained from $G$ by recursively joining pairs of nonadjecent vertices whose degree sum is atleast $n$ untill no ...
2
votes
1answer
43 views

Give me an example of a graph that has a Hamilton path that cannot be found with a greedy heuristic.

Give me an example of a graph that has a Hamilton path that cannot be found with a greedy heuristic. I have yet to find a graph that can fulfill these requirements, I thought a Peterson graph might ...
0
votes
1answer
68 views

Extraneous edges in hamiltonian graphs

I was wondering if this is already a solved question, it would save me a bunch of time if it is. Is it the case that in an undirected hamiltonian graph with N nodes, if some subset of our N nodes has ...
1
vote
0answers
82 views

A contradictory relation between probability and number of paths

Consider an urn containing $c$ balls, $\alpha$ of which are red, $\beta$ of which are blue, and $\gamma$ of which are green, and $\alpha+\beta+\gamma=c$. We perform $n$ trials with replacement of one ...
0
votes
3answers
301 views

Is any tree a Hamiltonian Graph

Hamiltonian path is a graph where every vertex is visited exactly once. And a tree can be anything, like a BST. I think that this answer is no because in a BST, it could find an element before ...
2
votes
1answer
160 views

3-connected planar bipartite graph without a Hamiltonian path

I'm stuck with exercise 18.1.5 of Bondy & Murty's Graph Theory book which asks for an example of a 3-connected planar bipartite graph on fourteen vertices that is not traceable (that is, which has ...
0
votes
0answers
39 views

Euler and Hamilton graphs

i would like to know about this. If it is Euler and Hamilton. As i see because it is $u_0$ unti $u_{19}$ it isn't Euler. Also, it is Hamilton because if we erase the edges we see it. Is this right or ...
3
votes
0answers
158 views

How to generate a Penrose tessellation around a given tile?

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it. The following picture illustrates the request: In this example, the starting tile is a "thin rhombus" (the pink ...
2
votes
1answer
245 views

Spiral path on a Penrose tiling

I would like to color a Penrose tiling by following a "spiral path", painting each tile according to a given color sequence. In this picture, I illustrate what I am looking for: The dashed line ...
3
votes
1answer
161 views

Properly stating a decision problem for a Hamiltonian cycle problem

I'm running an algorithms seminar and I'm trying to express the Hamiltonian cycle problem in a new way that is exciting to students. I know that many of them play a game called Hearthstone and I'm ...
1
vote
1answer
162 views

Counting Hamiltonian cycles in a graph

Given a graph $G = (W \cup U, E)$ where $W = \{w_1, w_2, ..., w_n\}$, $U = \{u_1, u_2, ..., u_n\}$ and $E = \{\{w_i, u_j\}: 1 \leq i, j \leq n\}$. The task is to calculate the number of Hamiltonian ...