Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [hamiltonian-path]

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

132 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
1answer
828 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
119 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
0answers
131 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 ...
7
votes
2answers
7k views

Proof of Hamilton Cycle in a Complete Bipartite Graph

For a complete Bipartite graph K(m,n) has a Hamilton cycle if and only if m=n. I want to know if the following proof technique is correct. My proof will consider using proof by contradiction. Assume ...
6
votes
0answers
69 views

Do the two order-4 Latin square graphs have the same number of Hamilton cycles?

A Latin square graph of a Latin square $L=(L_{ij})$ of order $n$ has $n^2$ vertices $(i,j)$ and edges between distinct vertices $(i,j)$ and $(i',j')$ whenever (a) $i=i'$, (b) $j=j'$, or (c) $L_{ij}=L_{...
6
votes
0answers
134 views

Is there a relationship between local prime gaps and cyclical graphs?

By defining the following algorithm I was able to generate some interesting graphs using the values of the gaps between consecutive primes: Start in any prime $p_i$, this will be the initial ...
5
votes
0answers
45 views

NP-Complete proof of deciding if a graph has another Hamiltonian Circuit

I need to prove as an exercise that the following problem is NP-Complete: Given a graph and an already existing Hamiltonian Circuit in that graph, decide if the graph has another Hamiltonian Circuit ...
4
votes
0answers
165 views

Prove or disprove that a graph made by $n$ straight lines is Hamiltonian.

Given $n$ lines, no two of which are parallel and no more than two intersect at the same point. Construct a graph with the intersection of lines as vertices and the line segments as edges. Prove or ...
4
votes
0answers
210 views

Hamiltonian path on a chessboard with prescribed endpoints

On an 8 x 8 chessboard consider two squares to be adjacent if and only if they share a common side. All paths below will consist of steps which join one square to an adjacent one. Under these ...
4
votes
0answers
47 views

Existence of fair parallel queues

I just spent a few days at a major theme park. The queue for one particular ride (involving pirates) bifurcated upon entry; the two sides wound independently through a maze and emerged next to each ...
3
votes
0answers
159 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 ...
3
votes
0answers
139 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 ...
3
votes
0answers
130 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 ...
2
votes
0answers
9 views

Hamiltonian paths in cubic graphs with cyclically edge connectivity at least 5

Definitions A cubic graph (simple) $G$ is a 3-regular graph. An edge cut $K$ is cycle separating if $G-K$ is disconnected and at least two components of $G-K$ have circuits. A graph is cyclically ...
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 ...
2
votes
0answers
28 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 ...
2
votes
0answers
133 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
255 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 ...
2
votes
0answers
52 views

Construct a graph with given properties

For any $k \ge 3$ construct a non hamiltonian, connected, $k$-homogeneous and two sided graph. I tried to use induction, but couldn't construct for $k=3$ or $4$. Any hints or advices appreciated
2
votes
1answer
128 views

Where are the Optimal Tours of TSPLIB 95 Instances?

I am looking for the optimal tours of the TSPLIB 95 instances as downloadable files. I have checked several places, but all lists I could find contain gaps, despite the fact, that all instances have ...
2
votes
0answers
16 views

Mathematical reasons whether to parametrize a shape-to-be-sampled-from via a path and sample its domain or do rejection sampling?

Suppose we have a subset $S\subseteq I_0\times I_1\times \dotsm \times I_{d-1}$ of a cartesian product of finite intervals $I_i\subseteq\mathbb{N}$, with $S$ defined by explicity specified computable ...
2
votes
0answers
234 views

Is the Traveling Salesman Problem with Precedence Constraints NP-hard?

I am searching for a proof of NP-hardness or dynamic programming solution to the Traveling Salesman Problem with Precedence Constraints (TSP-PC). So far I could not even find any proof that proves the ...
2
votes
0answers
70 views

Complementary Hamiltonian cycle in hypercube

I want to prove that every hypercube $Q_n$ where $n$ is even has a cycle where the vertices with the greatest possible distance ($n$) in the hypercube also have the greatest possible distance on the ...
2
votes
0answers
327 views

cut-vertex and Hamiltonian graphs

Given a graph $G$ with no cut-vertices, does it directly imply that $G$ is Hamiltonian? It is known that if a graph $G$ is nonseparable (thus, no cut-vertices) then every two distinct vertices in $G$ ...
2
votes
0answers
36 views

graph is Hamiltonian if the number of vertices with degree at most d is less that d

A graph, $|G| \geq 3$ such that $\forall d < n/2$ , $|\{v \in V(G) : deg(v) \leq d\}| < d $ then G has a Hamilton cycle. I'm not sure where to start, or what the second requirement suggests.
2
votes
0answers
107 views

$ \forall n \in N$ edges of $K_{2n+1}$ can be partitioned to hamiltonian cycles.

A hamiltonian cycle is a cycle which visits each vertex of the graph exactly once. A hamiltonian path is a path which visits each vertex of the graph exactly once. We need to prove that: 1-...
2
votes
1answer
3k views

Prove Dirac's Theorem by induction on the number of vertices

Dirac's Theorem says: If a connected graph $G$ has $n \ge 3$ vertices and $\delta(G) \ge \frac{n}{2}$, then $G$ is Hamiltonian. Now I want to prove this theorem by induction on $n$. For $i=3$,...
2
votes
0answers
166 views

Any graph from the Petersen graph has a hamiltonian cycle if one edge is added

Prove that any graph that can be obtained from the Petersen graph by adding one extra edge has a Hamiltonian cycle. So I've found that removing any vertex yields a Hamiltonian cycle -- I'm not sure ...
2
votes
0answers
279 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
0answers
1k views

Identifying Hamiltonian Systems with Phase Portrait

the following is a homework question (that isn't going to be graded) and I'm not sure how to do it. I know that the solution trajectories cannot cross the H(x,y)=constant curves, but I'm not sure how ...
2
votes
0answers
72 views

Example of a series parallel graph with toughness greater than $\frac{4}{7}$

Can anyone lead me to an example of a "more than $\frac{4}{7}$ tough series parallel graph"? Graph toughness is defined as $T = \min \left\{\frac{|a|}{\omega{(G\backslash A)}}\right\}$ over all cut ...
2
votes
0answers
328 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,...
2
votes
0answers
85 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
0answers
101 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 $...
2
votes
1answer
248 views

Classification of maximally non-hamiltonian graphs?

A graph is called maximally non-hamiltonian, if it does not contain a hamilton-cycle, but no edge can be added without creating a hamilton-cycle. In other words, every pair of non-adjacent vertices ...
1
vote
1answer
105 views

Random Tournaments

A tournament is a directed graph in which every pair of vertices has exactly one directed edge between them—for example, here are two tournaments on the vertices {1,2,3}: (1,2,3) is a Hamiltonian ...
1
vote
1answer
30 views

Hamiltonian cycles in balanced bipartite graph - proof of theorem

does anyone have an idea how to proof this theorem? Let $B$ be a balanced bipartite graph of order $2n$, $n ≥ 2$, as defined below and $s, t$ be two integers in $[0, n − 1]$. Then $D_s ∪ D_t$ forms a ...
1
vote
0answers
51 views

Algorithm to construct $k$ edge-disjoint Hamiltonian cycles

Consider an undirected graph $G=(V,E)$, where $V=\{1,2,\ldots, n\}$, and initially $E=\varnothing$. Now take the following steps: In the $1$st round, add undirected edges $(1,2)$, $(2,3)$, $\ldots$, $...
1
vote
0answers
40 views

Hamilton cycle problem on group's Cayley graph. Determining a function $G^n \to \Bbb{Z}[G]$.

Let $G$ be a finite group and $G^n$ be the direct product of $n$ copies of $G$. Let $f_g: G^n \to \Bbb{Z}, \forall \ g\in G$ be such that there exists at least one $x \in G^n$ such that $f_g(x) = 1, \...
1
vote
0answers
41 views

Efficient hamiltonian path through neighboring squares

My knowledge of Number/Graph theory is very limited. I'm sorry if someone can find this answer posted elsewhere quickly, I spent some time searching but don't know enough to know what to search. The ...
1
vote
0answers
47 views

Symmetric difference of Hamilton circuits in planar cubic graphs

The answer to math.stackexchange.com/questions/3235317/every-cubic-3-connected-hamiltonain-graph-has-three-hamiltonian-cycles-with-spec?rq=1 points out that the cube graph contains no three Hamilton ...
1
vote
0answers
24 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 ...
1
vote
2answers
199 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
0answers
32 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

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 ...
1
vote
0answers
38 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| ...
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 ...
1
vote
0answers
78 views

Questions about an “almost” 4-connected graph

How would this graph be classified? And what properties does it have? What would be a natural thing to study with this graph? I know it has 40 nodes. It's undirected. It's planar if I'm not mistaken. ...
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
0answers
236 views

Show the NP completeness of Hamiltonian Path with the knowledge of an directed Euler graph

I'm interested in the idea behind a NP completeness problem. It should be checked that Hamiltonian Path is in NP. As an indication, the problem Euler graph is in NP. Definition of Euler graph: An ...