Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
51 views

Give two distinct codes for $n = 4 $

gray codes for $n = 4 $. Attempt : The codes for $n = 4 $ : $0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$ $0000, 0001, 0011, 0010, 0110, 0111, ...
1
vote
1answer
144 views

Hamiltonian cycle that contains a specified edge in a 3-connected cubic bipartite planar Hamiltonian graph

Assume that we have a 3-connected cubic bipartite planar graph with a Hamiltonian cycle. That graph must have at least 4 Hamiltonian cycles, because of Theorem 1 and Theorem 10 of this paper. I would ...
1
vote
1answer
233 views

A biconnected bipartite non-Hamiltonian graph?

So I'm trying to find a biconnected bipartite non-Hamiltonian graph and here's what I found: http://i.imgur.com/thUI0tn.png There's no Hamiltonian cycle and we can split the vertices into two even ...
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$,...
3
votes
3answers
3k views

Hamilton paths/cycles in grid graphs

Let G be a grid graph with m rows and n columns, i.e. m = 4, n = 7 is shown here: For what values of m and n does G have a Hamilton path, and for what values of m and n does G have a Hamilton cycle? ...
3
votes
1answer
184 views

Minimum number of Hamiltonian paths in a strongly connected tournament on $n$ nodes

For $n\ge3$ let $a(n)$ be the minimum possible number of Hamiltonian paths in a strongly connected tournament on $n$ nodes. What is a good (or at least nontrivial) lower bound for $a(n)$? What is a ...
2
votes
0answers
155 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 ...
4
votes
1answer
12k views

How many Hamiltonian circuits are there in a complete graph with n vertices? [duplicate]

How many Hamiltonian circuits are there in a complete, undirected and simple graph with $n$ vertices? The answer written in my book is: $$\frac{\left(n-1\right)!}{2}$$ What is the combinatorial ...
1
vote
1answer
81 views

Hamiltonian paths of the Hoffman-Singleton graph?

Does anyone know how many Hamiltonian paths of the Hoffman-Singleton graph there are, or how I might go about figuring that out?
12
votes
1answer
9k views

Prove that every tournament contains at least one Hamiltonian path.

A tournament is a directed graph with exactly one edge between every pair of vertices. (So for each pair (u,v) of vertices, either the edge from u to v or from v to u exists, but not both.) ...
1
vote
1answer
618 views

hamiltonian and eulerian tour?

So, let's say I have a complete bipartite graph with vertex set V into two sets V1 and V2. The question is: for which values of m and n does a complete bipartite graph have an Eulerian tour that ...
1
vote
2answers
832 views

Prove that every 3-regular graph that contains a Hamiltonian cycle is always 3-edge colorable

A graph $G$ is $k$-edge colorable if there exists a function $f\colon E(G) → [k]$ s.t $f(e) \neq f(e')$ whenever $e$ and $e'$ share a vertex. A Hamiltonian cycle in an $n$-vertex graph is a sub-graph ...
3
votes
1answer
4k views

How To Tell If A Graph is A Hamiltonian?

So, I can look at this graph and tell that it is not a Hamiltonian, but I do not know the actual mathematical reason why. I can see that if you start on one vertex, then it would be impossible to ...
2
votes
1answer
66 views

Paths of a Cycle

I'm thinking through a problem, and I was having some trouble - I was wondering if I could get some help. The problem is: Let $u$ and $v$ be adjacent vertices in the cycle $C_5$. How many $(u,v)$-...
1
vote
1answer
35 views

When can $K_{m,n}$ be factorized into Hamiltonian paths

The question is as follows: Are some good necessary and/or sufficient conditions known for when can $K_{m,n}$ be factorized into Hamiltonian paths? In other words when can we have an edge ...
0
votes
1answer
96 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 ...
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(...
0
votes
0answers
24 views

number of edges to build all hamiltonian paths in complete digraph

I'd like to compute the number of edges necessary to build all Hamiltonian paths in a complete digraph. My thoughts so far: Let $N$ be the number of nodes. number of Hamiltonian paths: $N!$ ...
0
votes
1answer
97 views

Hamiltonian Ore Property Proof, why must be connected?

If G has order $n \ge 3$ and for all pairs of distinct vertices $x$ and $y$ that are not adjacent, $deg(x)+deg(y) \ge n$ then the graph is Hamiltonian. Here is the beginning of the proof: We ...
0
votes
2answers
90 views

Meeting People at a Party Hamiltonian Graph

Ten people came to my party. Each person meets at least 6 other people, except for my friend Ben who only meets four people. We make a graph H where each person is represented by a vertex, and put an ...
1
vote
1answer
360 views

Show that there is a path of length k in G

Let G be a connected simple graph with $n \geq 3$ vertices. Suppose that there is a positive integer $k \leq n$ such that $d(u) + d(v) \geq k$ for every pair of non-adjacent vertices $u$ and $v$. Show ...
0
votes
1answer
566 views

dirac's theorem not work

I am studing graph theory specifically hamiltonian cycles I have a doubt with a exercise, it is a connected simple graph with 13 vertices, the book says that this graph has a hamilton cycle(truly it ...
1
vote
2answers
797 views

Hamiltonian and non-Hamiltonian connected graph using the same degree sequence

I'm trying to find out if it is possible to construct a connected Hamiltonian and a connected non-Hamiltonian graph using the same degree sequence. For disconnected graphs it would be easier, I could ...
2
votes
3answers
548 views

prove that a graph with p vertices and $2+(p-1)(p-2)/2$ edges is hamiltonian

A Hamiltonian graph is a graph which has a Hamiltonian cycle. A Hamiltonian cycle is a cycle which crosses all of the vertices of a graph. According to Ore's theorem , if $p \ge 3$ we have this : ...
2
votes
1answer
222 views

Hamiltonian cycle [closed]

Assume $A_k$ be an undirected graph with $2^k$ vertices, $\forall k > 1$,$ k \in Z^+$. We use k-digit binary bit strings to label the vertices of $A_k$, where the labels of adjacent vertices diff ...
1
vote
1answer
203 views

Hamiltonian Graph Problem

I've been going about the proof of the Snark Graph's (https://en.wikipedia.org/wiki/Snark_(graph_theory)) non-Hamiltonicity. I understand that a snark is connected, bridgeless ( removing any edge ...
2
votes
1answer
137 views

Pullback of a Hamiltonian

I understand that a Hamiltonian vector field $H$ creates a Hamiltonian flow $\phi_t$. Now, in order to prove that the Hamiltonian is conserved one uses the following \begin{eqnarray*} \frac{d}{dt}\...
1
vote
2answers
591 views

Graph theory, graph coloring, hamilton

A simple graph G has $14$ vertices and $85$ edges. Show that G must have a Hamilton circuit but does not have an Euler circuit. My attempt: to be hamilton circuit, each should have degree at least $...
0
votes
2answers
58 views

Show that $G=(V,E)$ with $|V| \geq 4$ and the property that for any three vertices, at least two edges are in $E$ is Hamiltonian [closed]

I can't solve the following combinatorics problem Let $G=(V,E)$ be a graph with $|V|\geq4$ and with the property that for any three of its vertices $u$, $v$ and $w$,at least two of edges $uv$, $uw$ ...
0
votes
1answer
1k views

Does this graph have Hamiltonian path and/or Eulerian paths?

For this graph, do Hamiltonian and Eulerian paths exist or not? Basic definition A cycle that uses every vertex in a graph exactly once is called a Hamilton cycle, and a path that uses every ...
4
votes
0answers
203 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 ...
0
votes
1answer
73 views

Do All Hamiltonian Paths in a Graph with Several Disjoint Ham-Paths Have the Same Number of Edges?

I understand that a HAM-Path must cover all vertices without necessarily touching all edges. But, if a graph has, lets say, 2 edge-disjoint HAM-Paths, will both of these paths touch the same amount of ...
0
votes
1answer
133 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 ...
-1
votes
1answer
37 views

If $G$ is $2r$-regular ($r \geq1$), $|V(G)|=4r+1$ and there is a simple cycle of length $4r$ then $G$ is Hamiltonian [closed]

How could I start my proof? I have drawn $G$ for $r=2$ but still have no clue how to kick off.
5
votes
1answer
481 views

A connected simple graph $G$ has $14$ vertices and $88$ edges. Prove $G$ is Hamiltonian, but not Eulerian…

A connected simple graph $G$ has $14$ vertices and $88$ edges. Prove $G$ is Hamiltonian, but not Eulerian. -I almost feel like you have to prove these two parts separately. I understand that to be ...
0
votes
1answer
31 views

Total Number of distinguishable paths

I found a lot of things distribing a number of paths across a grid, but not quite what my question is. I'm looking for the total number of distinguishable paths through X number of points. For example,...
1
vote
2answers
297 views

Prove that $G$ with 21 vertices with at least 200 edges is Hamiltonian

I'm stuck with this question. 1. Let G be a simple graph on 21 vertices with at least 200 edges. Show that G is Hamiltonian. I tried to use Dirac's theorem to prove it but it is inconclusive because ...
0
votes
1answer
760 views

Eulerian and Hamiltonian graphs with given number of vertices and edges

I have an assignment for next week and I'm stuck with these two questions : a) Let G be a simple graph on 8 vertices with exactly 25 edges. Can G be Eulerian? How about with 24 edges? What I did : ...
1
vote
1answer
2k views

The number of Hamiltonian cycles in the complete bipartite graph

I know that in the complete bipartite graph $K_{n,n}$ , there is $\frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to ...
-2
votes
3answers
299 views

Two questions about eulerian and hamiltonian graphs.

I have 2 questions in graph theory. $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $Graph\ 1$ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $Graph\ 2$ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ ...
0
votes
1answer
98 views

Correctly quoting a Hamilton Circuit

This might come across as a slightly petty question. Apologies for this, I am only asking as I have an exam on Graph Theory soon and want to make sure I do things correctly. The definition of a ...
1
vote
1answer
411 views

Hamilton cycles for bipartite graphs

I know that a hamilton cycle exists for a bipartite graph $K_{m,n}$ if and only if $m=n$ But my question is why is it not possible to have a bipartite graph if $m=n=1$ I mean we would go from $x$ to ...
0
votes
1answer
60 views

Traveling Salesman with exceptions

Assume a regular TSP problem with n cities. However, in this particular problem, we do not have to visit all the n cities, only a specific subset of them, m, where m<=n. The cities in n but not in ...
0
votes
1answer
319 views

Is it necessary for hamiltonian cycle to cover all the vertices of the graph??

I have read the definition on wikipedia and it says: In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each ...
1
vote
0answers
117 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
1answer
200 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
0answers
995 views

Ore theorem vs Dirac theorem- when to use what?

Yesterday I asked a question about how to find hamiltonian paths and circuits in a graph, and I got the following answer: According to the theorem of Ore (to find paths): Let $G$ be a (...
0
votes
1answer
1k views

can we use vertex degree to detect hamilton path and hamilton circuit?

Hamilton path: goes through every node/vertex exactly once. Hamilton circuit: goes through every vertex exactly one and ends at the starting node/vertex. So i am wondering is possible to use degree ...
4
votes
3answers
4k views

Graph Theory: Trees, leaves and cycles

So, a vertex is called a leaf if it connected to only one edge. a) Show that a tree with at least one edge has at least 2 leaves. b) Assume that G = (V, E) is a graph, V ≠ Ø, where every vertex ...
5
votes
1answer
65 views

Is there a path through the “flipbook” of the game 504?

Inspired by discussion on this forum. For background, the game 504 is named as such because there are 504 possible "variations" formed by picking 3 modules from a possible 9 (where order is important)....