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.

0
votes
0answers
13 views

Finding a Hamiltonian Cycle from a perfect matching on a the bipartite graph

A disjoint vertex cycle cover can be found by a perfect matching on the bipartite graph constructed from the original graph (L) and its copy (R) and with L original graph edges replaced by ...
0
votes
1answer
38 views

How do we know that the prime sum graph defined in this paper has a perfect matching?

https://arxiv.org/pdf/1804.07104.pdf I am reading this paper and trying to understand why Theorem 1.1 guarantees a perfect matching for the prime sum graph as stated at the bottom of page 2. Can ...
0
votes
0answers
11 views

Determine the minimum number of robot teams

I have completed parts $a$ and $b$, but I am stuck on how to show my work for part $c$. I believe the minimum number of robot teams is $3$, but I'm not sure how I got that answer. How do I start this ...
-1
votes
0answers
38 views

Proving that every tournament contains at least one Hamiltonian path - without using induction

I want to prove that every tournament contains at least one Hamiltonian path. (This question has been asked and answered here Prove that every tournament contains at least one Hamiltonian path. but ...
0
votes
1answer
22 views

Traveling sales man with alternating groups of destinations.

I am looking for an algorithm to determine the best route where the groups of destinations alternate. For example: I have three stores and three warehouses. So I would like to visit a warehouse first,...
5
votes
2answers
213 views

Playing Doublets with the Primes

Lewis Carroll's famous game of Doublets is well known. In it you are asked to transform a given word into another by changing only one letter at a time, forming a genuine new word (not a proper name) ...
1
vote
1answer
33 views

Determine if a Hamiltonian Cycle exists?

Suppose I have a graph $G=(V, E)$. Removing a subset $R$ of edges from $G$ results in a new graph $G^\prime=(V, E\setminus R)$. The maximum number of edges in $R$ is $|E|$. Suppose I have the graph $G^...
1
vote
0answers
34 views

How to show that there exists a tournament of size n with a certain number of Hamiltonian paths? [duplicate]

Assuming a tournament of size $n$ is a choice of orientation for each edge of $K_n$, show that there exists a tournament of size $n$ with at least $\dfrac{n!}{2^{n-1}}$ Hamiltonian paths. This ...
0
votes
1answer
22 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 ...
1
vote
1answer
43 views

Proof that if graph has $\frac{(n-1)(n-2)}{2} + 2$ edged then contains hamiltonian cycle

Proof that if graph has $\frac{(n-1)(n-2)}{2} + 2$ edged then contains hamiltonian cycle I think that it is good to use there induction: Let check base of induction. For $ n= 3 $ I have $$ |E| = \...
1
vote
0answers
21 views

Chance of not finding an alternating Hamiltonian path in a colored graph in $n$ random walks

Introduction Given a random graph which can be constructed as follows: generate $s$ pairs of unconnected black edges and $2 \cdot s$ vertices connect these black edges using red edges, where the ...
0
votes
1answer
22 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$ $(...
1
vote
1answer
29 views

Finite Graph With Degree $\geq 2$

Show that a finite graph with all vertices with degree $\geq 2$ has a cycle that contains a vertex which is non-adjacent to any other vertices not contained in the cycle. I tried to start at an ...
0
votes
0answers
31 views

Hamiltonian Cycle with n vertex graph

Let a n-vertex graph such that every pair of not adjacent vertices a & b has degree(x) + degree(y) $\geq$ n. Show the graph contains a Hamiltonian cycle. By dirac's thm, a simple graph with n ...
0
votes
0answers
51 views

Reduce Hamiltonian Path Decision Problem To Hamiltonian Cycle Decision Problem

Person A requires that he determine whether or not a particular graph G = (V,E) has a Hamiltonian path from vertex a to vertex b. His colleague Person B has implemented a function that takes an ...
0
votes
0answers
14 views

Proof of equivalence of S-TSP solution with TSP solution (metric instances)

I am wondering where could I find proof for following S-TSP to TSP transformation. S-TSP (Steiner Travelling Salesman Problem) def: Let $G=(V, E)$ be a non-directed weighted graph. Let $V' \subset V$ ...
0
votes
1answer
32 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$ ...
3
votes
1answer
109 views

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
21 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
32 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 ...
1
vote
1answer
69 views

How to convert a maximal planar graph to a regular planar multigraph?

Given a maximal planar graph (coming from the convex hull of a set of points on a sphere), I want to add edges until it is regular (all vertices touch the same number of edges), while keeping it ...
0
votes
3answers
15 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
187 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
51 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
36 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
21 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
29 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
30 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
23 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
34 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
19 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
41 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
38 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
59 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
52 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
74 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
20 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
32 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
93 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
34 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
63 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
19 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 $...
7
votes
1answer
184 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
38 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
30 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
32 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
64 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
81 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?