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.

1
vote
2answers
191 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 ...
1
vote
2answers
46 views

Hamiltonian circuits / graphing

Can someone tell me if I'm correctly doing these graphs for Hamiltonian circuits? I know that you start at the root node and show the path "back" in a tree. But what if it crosses and such. I'm just ...
1
vote
2answers
626 views

Hamiltonian path in a complement of a tree

T is a tree on n-vertices for which the greatest degree is smaller than n-1, prove that the complement of T has a Hamiltonian path. I was trying to achieve Ore's inequality, this is what I have ...
0
votes
2answers
61 views

Number of Hamiltonian Cycles in planar chordal graph

I have a given planar chordal graph $G$. Due to the construction of $G$ I know that there exists at least one Hamiltonian cycle in $G$. My question is: How many Hamiltonian cycles are in $G$? (an ...
0
votes
2answers
32 views

bulding a Hamilton circuit in a given graph

Let G be an undirected graph with k components. assume that every components consist a Hamilton circuit. prove that by adding exactly k edges to the graph you can achieve a connected graph with ...
0
votes
2answers
126 views

How many Hamiltonian cycles are there in $K_{10,10}$?

I want to calculate the number of Hamiltonian cycles in $K_{10,10}.$ Could anyone help me? I think in $K_{10}$ we have $9!$ Hamiltonian cycles.
0
votes
2answers
491 views

Examples of non-hamiltonian decomposable graphs

Good Afternoon! I read that Line graph of the Petersen graph is 4-regular 4-edge-connected and non-hamiltonian decomposable. Does someone knows examples (or references) of non-hamiltonian ...
1
vote
1answer
198 views

when are Kneser graphs connected?

For the kneser graphs $K(n,k)$. The vertices of $K(n, k)$ are all $k-$subsets of the set $\{1, 2 ,......,n \}$ and two vertices are adjacent to each other if and only if the $k-$subsets are ...
0
votes
1answer
23 views

Hamiltonian Cycles of a graph

Prove if this statement is true: every graph consisting of two edge-disjoint Hamiltonian paths contains a Hamiltonian cycle. Two edge-disjoint Hamiltonian paths means all vertices can be connected ...
0
votes
1answer
24 views

Short explanation for hamiltonian cycles in $Q_3$

The task is to find the count of hamiltonian cycle in $Q_3$. So I know the answer is $6$, but i don't know why or how to get it. My first attempt was simple: I start from edge $6$, and I have $3$ $(...
0
votes
1answer
23 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
35 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
1answer
32 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
1answer
296 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
1answer
95 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 ...
0
votes
1answer
78 views

Are Hamiltonian trajectories geodesics on the cotangent bundle?

Suppose we have a Hamiltonian dynamics on a phase space, whose base space is also a Riemannian manifold. I was wondering if the Hamiltonian trajectories are whether geodesics or only locally geodesics ...
0
votes
1answer
267 views

Proof with induction on $n$ so that the complete graph $K_n$ has $(n-1)!$ hamilton cycle for all $n \geq 3$.

I came up with this solution, but I'm not sure if it's right. Could you check if there is something missing? In the Hamilton cycle, every visit to a node is only exactly one time. Base case: $K_n$ ...
0
votes
1answer
74 views

Finding Hamiltonian cycle for $N\times M$ grid where $N$ is even

This is the solution provided for the problem. However when I follow it, I am not getting the correct path. I assumed $N=4$ and $M=3$ and started with $k=0$ and got this path: $$(0, 1) \to (0, 2) \to ...
0
votes
1answer
227 views

constraints to the hamiltonian path: can one tell if a path is hamiltonian by looking at it?

A few days ago, the channel Numberphile released this video on the square-sum problem. The show later released this follow-up video on how they proved that every number from 25 to 91 can have ...
0
votes
1answer
44 views

$K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of Hamiltonian cycles

Show that (the edges) in the complete graph $K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of Hamiltonian cycles. Further, show that (the edges) in the complete graph $K_n$ ...
0
votes
1answer
1k views

Hamiltonian Path to Hamiltonian Cycle reduction

I have to show that HP polynomially transforms HC by following steps: (1) Construct a polynomial transformation f from HP to HC. (2) Show for all graphs G that G ∈ YHP ⇒ f(G) ∈ YHC. (3) Show for all ...
0
votes
1answer
692 views

Polynomial time reduction Hamiltonian path to TSP

is there a polynomial time reduction from Hamiltonian Path to TSP? If so, could you tell me? Thank you in advance! Toby
0
votes
1answer
250 views

Variation of TSP - Revisit Nodes

I have a problem where I have an symmetric graph and I want to find that shortest path that visits every node at least once (not exactly once). In order to solve this problem, I have found that we ...
0
votes
1answer
93 views

Unique Extremal Non-Hamiltonian Graph

Let $G$ be a graph on $n$ vertices with size at least ${n\choose 2} - (n-2)$. Show that $G$ is Hamiltonian. What is the unique Extremal graph? The first part I did. I even know the Extremal graph ...
0
votes
1answer
131 views

Smaller Cycle Inside Hamiltonian Graph

It seems obvious to me that a cycle $C_k$ in a graph on $n$ vertices ($n > k$) cannot feature in a Hamiltonian cycle for the graph, but I'm having trouble writing it down in a rigorous fashion. Any ...
0
votes
1answer
199 views

Dijkstra’s algorithm / path is this done correctly?

im doing this assignment and it seems as if my teacher has made a mistake. according to me in order to find the minimum spanning treee from a-z , you start from a and then go to : a,f,d,c,b,e,z,g ...
0
votes
1answer
137 views

Hamiltonian bipartite graphs

Let $G$ be a bipartite graph with $n$ vertices and independent sets $U$ and $V$ such that $\vert U\vert=\vert V\vert=k=\frac{n}{2}>2$. I want to show that if $d(v)>\frac{k}{2}$ for every ...
-2
votes
1answer
63 views

Traveling salesman problem

Consider the traveling salesman problem with five cities. The cities are called $\text{A,}$ $\text{B,}$ $\text{C,}$ $\text{D,}$ and $\text{E}$. Here is the mileage chart for the cities. $$\begin{...