Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
6
votes
2answers
362 views

How many routes are there from $A$ to $B$ that cross every node exactly once?

Imagine an $n \times n$ grid, we start on one corner of the grid in square $A$, and need to reach the opposite corner to square $B$. The rules are, you can only move to an adjacent square, you can't ...
0
votes
2answers
86 views

Ambiguity regarding the definition of 'path' in graph theory

While going through the Introductory chapter of 'Graph Theory' by Bondy and Murty, I came across the definition of 'path' that says it's a sequence of vertices in such a way that two vertices are ...
0
votes
1answer
200 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 ...
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 ...
0
votes
0answers
30 views

Do hamiltonian paths exist on n-valent, simple, connected, planar graphs, where n>2?

I don't know to much about graph theory, so was wondering about the posted question. If it is too much perhaps you may know the answer if n is even? Any help is appreciated. Also, this is my first ...
2
votes
3answers
1k views

Generate all De Bruijn sequences

There are several methods to generate a De Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length $n$...
0
votes
1answer
138 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 ...
0
votes
1answer
45 views

Hamiltonian graphs of integers $n$

For which integers of $n$ is $K_{4,n}$ Hamiltonian? I know it is a complete bipartite graph, and there are $4$ vertices on one end and $n$ in the other. My guess is that $n$ would be the set: $\{4,5,6,...
1
vote
1answer
895 views

Given that Minimum Spanning Tree is NP-complete show that Hamiltonian Cycle is NP complete

So first of all I know finding MST is in P and is not NP complete. But I checked last year exams from my University and there is a problem: Given that Minimum Spanning Tree is NP-complete show that ...
1
vote
2answers
105 views

Is showing a graph is non-Hamiltonian NP-Complete?

Show that graph is not Hamiltonian. Is this an NP-complete problem? My guess is that this is not an NP-complete problem, because we can run DFS and check it. Like, if we have a Hamiltonian cycle ...
1
vote
1answer
254 views

In a connected graph, if the maximum path you could make is of length 100, and there are two paths of length 100, aren't they the same path?

Here's the question: Let G be a connected graph. (Remember that this means that every two vertices of G can be joined by a path starting at one and ending at the other.) Suppose also that G ...
0
votes
2answers
2k views

Every tournament conatins a hamiltonian path - question about the proof

There is a proof that every tournament contains a Hamiltonian path and it goes as follows: Let $P$ be a path of greatest length in a tournament $T$, say $P = (v_1,v_2,...,v_k)$. Let's say that there ...
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 ...
0
votes
0answers
47 views

Cubic 3-edge connected graph which is neither hamiltonian nor hypohamiltonian

Is there such a thing as a cubic 3-edge connected graph which is neither hamiltonian nor hypohamiltonian? Intuition says yes, but I'd like a confirmation (and an example, if possible). Thank you!
2
votes
0answers
261 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 ...
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.
1
vote
2answers
630 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
495 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 ...
0
votes
0answers
79 views

Insertion into an optimal route – is it still optimal?

I have been pondering this question for a little while and my colleagues seem unsure as well. The problem involves a vehicle that must visit several waypoints contained in a large road network. The ...
2
votes
1answer
347 views

Is there any regular, balanced, connected bipartite graph that does not contain any Hamiltonian cycle? [duplicate]

In a set of balanced, connected bipartite graphs, all with regularity $r \ge 2$, is it possible that there exists a bipartite graph that does not contain a Hamiltonian cycle ? My argument: The ...
6
votes
2answers
388 views

Finding a Hamiltonian cycle for the set of RGB colors?

I'm consulting on an art project where a question about colors came up. Consider the RGB colors as a graph. The nodes are ordered triples $(r, g, b)$ where each entry is an integer from $[0, 255]$....
8
votes
2answers
375 views

Hamiltonian Weighted Graph and Decision Problems

I ran into a question on previous Mid-Exam. anyone could clarify me? Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a Complete Weighted ...
3
votes
1answer
178 views

min degree at least $n+1/2$, every edge on Hamilton cycle

Show that in a graph $G$ if $\delta(G)\ge {n+1 \over 2}$ then every edge $e=(u,v)$ is a part of a Hamilton cycle. Line of thinking: $G'=G/e$ has a Hamilton cycle by Ore's theorem ($d(u)+d(v)\ge n$ ...
0
votes
1answer
2k views

Reduce Hamiltonian Path to CNF SAT

I'm trying to figure out how to reduce a 5 vertex graph to a Boolean equation that will answer if the graph contains a Hamiltonian path. For a Hamiltonian Path to be present in a graph: Each vertex ...
0
votes
2answers
42 views

Hamiltonian cycle in shared-digit graph

Let G be a graph. The Vertices of g are the possible trios made out of the numbers 1-7. 123 124 etc (total of 7 choose 3). Two vertices have an edge between them if and only if the have one and only ...
0
votes
1answer
475 views

Probability of choosing a graph with Hamiltonian cycle

Given $N$ labeled points in a plane one can construct $2^{N(N-1)/2}$ graphs(Unweighted, undirected) with them. Is there any theorem that gives the probability of choosing at random from these a graph ...
0
votes
1answer
395 views

Showing that a graph doesn't contain a Hamiltonian ccle

In the article here it says that A Hamilton circuit cannot contain a smaller circuit within it. ? What is meant by this? I thought this meant that for example if ...
4
votes
1answer
471 views

How many ways to visit 4 cities so that each city is visited exactly 4 times without visiting the same city twice in a row?

The inclusion-exclusion principle doesn't work. Example of good path is: $$ 1\to 2\to 1\to 4\to 3\to 2\to 1\to 4\to 3\to 2\to 1\to 3\to 2\to 4\to 3\to 4$$ This one isn't: $$ 1\to 2\to 1\to 1\to 3\...
6
votes
1answer
6k 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 ...
2
votes
0answers
942 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 ...
0
votes
1answer
66 views

Hamiltonian graphs and card shuffles

I am solving the example on Hamiltonian graphs: We have 3 players of unique a game, there are 57 special cards. We know that by the rules of the game we can play only react to one card by 30 ...
2
votes
1answer
206 views

Hamilton Path Polytope

How can someone prove that the $\{dim(H)=\frac{n(n-1)}{2} uncorrect\ see\ update\}$ where $H$ is the Hamilton path polytope of a complete graph $K_n$, that consists of vertices $x\in\{0,1\}^{\mid E\...
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 ...
1
vote
1answer
636 views

Find simple path with the largest sum of weights

In the longest path problem, given a weighted graph G and a starting node v0, find the simple path starting with v0 with the largest sum of weights. Show that the longest path problem is NP-hard in ...
0
votes
1answer
353 views

Definition of a tree and 2 cycles

I've run into a problem with the definition of a tree, and possibly more generally with the definition of a cycle. I've run into the problem a few sections after we talked about trees, and I never ...
1
vote
1answer
174 views

Upper bound for the number of hamilton cycles in a cubic graph

Wikipedia states, that it has been proven, that there are at most $1.276^n$ hamilton cycles in a cubic graph with $n$ nodes. This upper bound is not valid for $n=6$. The values I found out using an ...
0
votes
1answer
26 views

Building a non-hamiltonian graph of $p$ vertices of $\frac{p-1}2$ degree each.

I want to build some graph with $p$ vertices all with degree of atleast $\frac{p-1}{2}$ that isn't hamiltonian. I imagine this is possible, but I can't seem to do it. Any suggestions? Perhaps looking ...
0
votes
1answer
153 views

$3$-connected non-hamiltonian graph with at most $3$ independent vertices

Is there a $3$-connected non-hamiltonian graph with at most $3$ independent vertices ? I checked the graphs upto $9$ vertices and the cubic graphs upto $18$ vertices and did not find such a graph. If ...
2
votes
1answer
87 views

Are “almost all” graphs hamiltonian?

Let $$p(n):=\frac{\text{number of hamiltonian graphs with $n$ nodes}}{\text{number of graphs with $n$ nodes}}$$ Since $883156024$ of the $1018997864$ graphs with $11$ nodes are hamiltonian, we have ...
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)...
3
votes
1answer
61 views

Least graph with exactly $2014$ hamiltonian circuits?

What is the least graph with exactly $2014$ hamiltonian circuits ? First of all, I am not sure, if for every natural number $n$, there is a graph with exactly $n$ hamiltonian circuits. Is that so, ...
-1
votes
1answer
161 views

Is this dot puzzle solvable?

Is it possible to connect all the dots with one line without touching the same point, going diagonally, or touching the black line? • • • • • • • | • • • • • • • • • • • • • • • • • • • • • • • • ...
0
votes
0answers
85 views

Graph with minimum degree $\ge 3$ and exact $1$ hamilton circuit

Enumerating the graphs upto $9$ vertices and the cubic connected graphs upto $18$ vertices, I did not find a graph with minimum degree $\ge 3$ and exact $1$ hamilton circuit. Is there a graph with ...
2
votes
1answer
239 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 ...
0
votes
1answer
214 views

Hamiltonian cycle on a subset of 2D points, constrained by a total length (traveling salesman variation)

We are given a list of 2d coordinates, each coordinate representing a node in a graph, and a scalar D, which is a constraint on total length of the cycle. The task is to find a Hamiltonian cycle on a ...
11
votes
2answers
749 views

Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle?

Can a bipartite graph with at least three vertices have the following properties simultaneously: Every vertex is the initial vertex of some Hamiltonian path. The graph contains no Hamiltonian cycle. ...
6
votes
1answer
81 views

Is this the smallest graph with the desired properties?

The above graph has the following properties : $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no hamiltonian cycle. $3$) It has no cycle of length $3$. $4$) It is planar....
3
votes
1answer
142 views

Is there a graph with these properties?

Is there a simple undirected graph with the following properties ? Each vertex has at least degree $4$ Each vertex is start vertex of some hamiltonian path The graph does not contain a hamilton cycle....
3
votes
1answer
333 views

Smallest non-hamiltonian k-connected graph

Let $G$ be a simple undirected $k$-connected graph with at least $k+1$ vertices. What ist the least number of vertices, $G$ can have, if it is not hamiltonian ? I know Tutte's theorem that every $4$-...
0
votes
1answer
184 views

Combinatoric Graph

Draw a graph whose nodes are the subsets of {a,b,c}, and for which two nodes are adjacent if and only if they are subsets that differ in exactly one element. (a) What is the number of edges and ...