Questions tagged [hamiltonian-path]
A path in a graph that visits each vertex exactly once.
378 questions
0
votes
1answer
18 views
Are Euler trails and tours of a graph the same as Hamilton paths and cycles of the corresponding “edge graph”?
Is knowing information about Euler paths and Euler tours about a graph $G$ the same as knowing information about Hamilton paths and cycles of the graph $H$ obtained from $G$ such that vertices of $H$ ...
0
votes
0answers
38 views
+50
How to calculate quantity of Hamilton cycles
If I have $n^2$ vertices and each vertex is adjacent to $2n-2$ vertices, how may I calculate the quantity of possible Hamilton cycles?
Would I need to modify the computation if I stipulated that I'm ...
0
votes
1answer
16 views
Graph which is Bipartite, has an Euler circuit, but not a Hamiltonian circuit
Is there a graph which is bipartite, has an Euler circuit, but not a Hamiltonian circuit?
I know the answer is yes, but if you consider something like this:
I don't think this would be bipartite, ...
0
votes
1answer
31 views
Prove that the connected circulant regular graphs of degree at least three contain all even cycles.
This is the question I am trying to solve, but while researching about circulant graph I came across Paley's graph of order 13.
Now clearly when looking at this graph which is an example of circulant ...
0
votes
3answers
14 views
Would removing the max weighted edge from a Hamiltonian circuit result in a Hamiltonian path?
If I have a Hamiltonian circuit, assuming that cutting the max weighted edge resulted in a Hamiltonian path.
Is it guaranteed that the path would be minimal too?
1
vote
2answers
183 views
Show that the line graph of any quasi-cyclic graph contains a Hamiltonian cycle.
The definition I have been given for a quasi-cyclic graph is as follows: a graph $G=(V, E)$ is quasi-cyclic if $1)$ it contains a unique cycle $C=(V(C), E(C))$ and $2)$ for each edge $xy$ in $E$ at ...
0
votes
1answer
30 views
Finding number of two cycle multi-graphs [closed]
Consider directed graphs on n labelled vertices {1,2,...n}, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many such graphs have exactly two ...
2
votes
1answer
42 views
Number of Hamiltonian cycles in a random graph
I want to show that $\mu_{n}(p)$, the expected number of Hamiltonian cycles in the random graph $G(n,p)$, is given by
$$\mu_{n}(p)=\frac{1}{2}(n-1)!p^{n}$$
We can easily show that the number of the ...
1
vote
1answer
35 views
Limiting behavior of the expected number of Hamiltonian cycles in the random graph $G(n, p)$.
So we have that the expected number of Hamiltonian cycles in the random graph $G(n,p)$ is given by:
$\mu_{n}(p)=\frac{1}{2}(n-1)!p^{n}$ for $n \geq 3$.
We now want to find lim$_{n\to \infty}\mu_{n}(...
1
vote
0answers
20 views
Combinatorial proof of Hamiltonian paths on the rook graph
We can be sure that number of Hamiltonian paths on the rook graph for any single cell on $n\times2$ chessboard equals
$$
H(n+1) = \sum_{k=0}^{n}
\binom{n}{k}
\binom{k}{\lfloor{\...
1
vote
1answer
23 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
0answers
17 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
22 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
32 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
11 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
18 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
38 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
36 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
44 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
48 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
59 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
19 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
29 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
80 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
32 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
56 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
17 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 $...
6
votes
1answer
144 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
37 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
29 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
31 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
57 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
1
vote
1answer
62 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
79 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
103 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
178 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
40 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
127 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
111 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
255 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
31 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
34 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
10 views
Pseudo hamiltonian connected property of a graph
Is there a connection between pseudo hamiltonian connectedness and hamiltonicity of graphs?
3
votes
1answer
32 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
54 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 ...
1
vote
2answers
65 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
66 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
70 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))+...
1
vote
0answers
66 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 ...
