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.

9
votes
0answers
113 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 ...
6
votes
0answers
76 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 ...
6
votes
0answers
67 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
131 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 ...
4
votes
0answers
159 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
195 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
45 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
144 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
130 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
126 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
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 ...
2
votes
0answers
21 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
78 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
0answers
50 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
0answers
15 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
215 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
65 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
257 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
95 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
0answers
153 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
253 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
925 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
276 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
80 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
89 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 $...
1
vote
0answers
22 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
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
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| ...
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
68 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
0answers
228 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 ...
1
vote
0answers
75 views

Minimum board size for knights tour to be possible

What is the minimum board size for a knight's tour: open or closed, to be possible. Edit: I want to write a program that can solve knight's tour for any board size. I want to implement a lower limit ...
1
vote
0answers
70 views

Directed Cayley Graph With No Hamilton Cycles

In the excellent Algebraic Graph Theory book by Godsil and Royle, they show that you can construct an infinite family of directed Cayley Graph (so vertex transitive) that are not Hamiltonian. The ...
1
vote
0answers
78 views

Find a Hamiltonian circuit in a given Hamiltonian graph.

I am wonder if there is a polynomial time algorithm(may be probabilistic) that can compute a Hamiltonian circuit in a graph which is known as Hamiltonian graph without other assumption. If there is,...
1
vote
0answers
24 views

Finite universal numbers

Given an alphabel $\Sigma$, a sequence $\bar{s}$ in $\Sigma^*$ is said to be k-universal if it contains all sub-sequences of $\Sigma^k$. I am interested by the smallest of these k-universal sequences. ...
1
vote
0answers
27 views

Graph Theory - Does a graph have an eulerian circuit if its edges can be divided into groups, each having a hamiltonian circuit?

Let $G=(V,E)$ be a graph. Its edges can be divided into several groups such that each group has a Hamiltonian Circuit of the original graph $G$. Does $G$ have an Eulerian Circuit? I said yes. ...
1
vote
0answers
77 views

Can it be proven that more than one vertex can individually be removed from a strong tournament and still be strong?

One vertex can be removed from the vertex set, V(T), of a strong tournament, T, so long as |V(T)| is greater than or equal to 4. Any strong tournament has (at least) one Hamilton for every k, where k ...
1
vote
0answers
36 views

Let $C_n$, $C_m$ two cycles, show that $C_n * C_m$ is hamiltonian. Conclude saying that if $G$ and $H$ are hamiltonian then $G x H$ is hamiltonian

Hi I need to prove this: Let $C_n$, $C_m$ two cycles, show that $C_n * C_m$ is hamiltonian. Conclude saying that if $G$ and $H$ are hamiltonian then $G x H$ is hamiltonian But i really don't know ...
1
vote
0answers
129 views

Knights tour dfs search with look ahead

After Using a basic depth first search I was wondering if there was any way to predict a dead end before one becomes apparent? As I know I can stop there becoming multiple dead ends as in a single ...
1
vote
0answers
137 views

Show that if any $k+1$ vertices of $k-$connected graph with at least 3 vertices span at least one-edge, then the graph is hamiltonian.

Show that if any $k+1$ vertices of $k-$connected graph with at least 3 vertices span at least one-edge, then the graph is hamiltonian. I know that a graph $G$ is said to be $k-$connected if there ...
1
vote
0answers
101 views

Proving a game has a winning strategy over a graph $G$ if and only if $G$ has no perfect matching

Two people play a game over a graph $G$ choosing alternately different vertices $v_1,v_2,...$ such that, for every $i>0$, $v_i$ is adjacent to $v_{i-1}$. The last player capable of choosing a ...
1
vote
0answers
56 views

What is the probability of no cycles length $n$ in a simple, directed Erdos-Renyi graph with $n$ vertices?

What is the probability of having no cycles with length $n$ (touching all vertices) in a simple, directed Erdos-Renyi graph with $n$ vertices? For example, if $n=2$, then the probability is $1-P(...
1
vote
0answers
101 views

Finding a Hamiltonian cycle for $Q_4$

A hyper cube $Q_n$ is a graph that have the length-n binary sequences as its vertices. Two vertices are adjacent if they differ in one entry. I found a Hamilton cycle for $Q_3$ as follows $$000 \to ...
1
vote
0answers
24 views

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that $$c(\tau(a),\tau(1))+\sum_{i=1}^{a-1} c(\tau(i),\tau(i+1))\leq b $$ Prove ...
1
vote
0answers
57 views

Least number $k$ , such there is no graph with $n$ nodes and $k$ hamilton-cycles

Let $f(n):=$min{ $ k \in N$: There is no graph with $n$ nodes and $k$ hamilton-cycles} for $n\ge 3$ The values I found out so far : $$f(3)=2$$ $$f(4)=2$$ $$f(5)=3$$ $$f(6)=9$$ $$f(7)=13$$ $$f(8)...
1
vote
0answers
157 views

Conditions for a $2$-connected graph to be hamiltonian?

Let G be a simple undirected graph. If G is connected, and every vertex has degree $2$, then G is hamiltonian. (In fact, G only consists of the hamilton-circle) Are there some weaker sufficient ...
1
vote
0answers
199 views

Complete tripartite graph hamiltonian

Let $G_{a,b,c}$ be a complete tripartite graph. For what values of $a, b$ and $c$ is $G_{a,b,c}$ Hamiltonian?
1
vote
0answers
412 views

Are there necessary and sufficient conditions of a graph to decompose into two Hamiltonian cycles?

Let $G$ be a graph. Definition: $G$ is decomposable into two Hamiltonian cycles if the edge set $E(G)$ can be partitioned into two disjoint Hamiltonian cycles. Obviously, if $G$ is decomposable into ...