Questions tagged [hamiltonicity]

For questions related to the Hamiltonicity of a graph.

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 views

Is there a connected graph where every vertex has degree k >1 with no Hamiltonian cycle?

I am trying to construct a simple connected graph where every single node has the same degree $k>1$ but without containing any Hamiltonian cycle. Take this simple example as shown in the images ...
JCr's user avatar
  • 93
3 votes
1 answer
34 views

Is There any Untraceable Generalized Petersen Graph?

The Petersen graph is one of the example of graph which is not Hamiltonian. Can we find an example among the generalized Petersen graph which doesn't have Hamiltonian path (untraceable)?
user966's user avatar
  • 1,939
2 votes
0 answers
72 views

Are Tutte's results still valid for planar graphs with multiple edges?

Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...
licheng's user avatar
  • 2,288
0 votes
1 answer
36 views

Does the operation stitch preserve non-Hamiltonicity?

A planar graph is triangulated if its faces are bounded by three edges. A triangle of a planar graph is a separating triangle if it does not form the boundary of a face. That is, a separating triangle ...
licheng's user avatar
  • 2,288
1 vote
1 answer
85 views

Does the graph have a Hamiltonian circuit or a Hamiltonian path?

Certain necessary conditions for a Hamiltonian circuit such as the graph being 2-connected, having zero pendants are met. Dirac's and Ore's theorem provide sufficient conditions, which are not ...
0x13's user avatar
  • 415
3 votes
1 answer
63 views

1-tough non-Hamiltonian graphs

The Petersen graph is a famous example of a 1-tough non Hamiltonian graph, and I stumbled across the following graph which also follows the property: . I found this example in a paper by V. Chvátal. ...
Kian Shah's user avatar
1 vote
1 answer
34 views

Hamiltonicity of bipartite graphs maximum degree $3$, where $X$ or $Y$ is a clique

I'm quite new to graph theory and NP-complete proofs. I stumbled across NP-completeness on hamiltonicity of bipartite graphs with maximum degree $3$ and was wondering whether the same applies to ...
Melo12's user avatar
  • 13
4 votes
1 answer
113 views

Construct some special non-Hamiltonian graphs.

The following theorem is well known. Theorem 1. If $G$ is a graph containing a set $S \subset V(G)$ such that $G-S$ has more than $|S|$ components, then $G$ is not Hamiltonian. We know the converse of ...
licheng's user avatar
  • 2,288
1 vote
1 answer
89 views

Find a minimum 2-connected 5-regular non-Hamiltonian graph

Inspired by the post. According to this paper, there are $k$-connected $k$-regular non-Hamiltonian graphs for $k=4$ and $k \ge 8$ but the other cases are not shown there. Now I need to construct a 2-...
licheng's user avatar
  • 2,288
1 vote
1 answer
66 views

Showing that a specific graph is not hamiltonian

I am supposed to show that the following graph is not hamiltonian. In the lecture I am attending to we have looked at only one criteria to determine if a graph is not hamiltonian which is that for $\...
Raoul Luqué's user avatar
0 votes
0 answers
39 views

Asymptotic approximation algorithms for TSP

I have been reading a lot about TSP approximation algorithms recently, and I noticed that most of the algorithms tend to fall under two general categories: some that have a guaranteed approximation ...
slithy_tove's user avatar
0 votes
0 answers
128 views

Show that a simple graph G, where the degree of all vertices are at least half of G's order, has a hamiltonian cycle

Consider a graph G on n vertices (n != 2) , where the degree of any given vertex is at least n/2. I am trying to prove it has a hamiltonian cycle. I tried proving that it has a spanning path, but ...
AlexandreAmaral's user avatar
2 votes
2 answers
214 views

Add a minimum of edges to make the graph Hamiltonian

We have graph $G=K_{9,15}$. I need to add some edges to it for make Hamilton Graph. So, we know: $$V(G) = 24,\ E(G) = 135. $$ Every vertex has to be equial or more than 12. (24 / 2). So the question ...
NoOneCare's user avatar
1 vote
1 answer
123 views

Non-Hamiltonian graphs with a certain minimum vertex degree

Show that there are non-Hamiltonian graphs of any even order $p ≥ 4$ satisfying $δ(G) = p/2 − 1$ and that there are non-Hamiltonian graphs of any odd order $p ≥ 3$ satisfying $δ(G) = \frac{p − 1}2$. ...
Kilkik's user avatar
  • 1,919
4 votes
1 answer
140 views

2-connected graph is Hamiltonian

I tried to prove this: If $G$ is a $2$-connected graph with independence number $2$, then $G$ is Hamiltonian. I was thinking to construct de hamiltonian cycle. We know that $G$ has independence number ...
TresTresUno's user avatar
0 votes
1 answer
34 views

Condition for a Hamiltonian cycle existing proof question

Let $G$ be a graph. If there exists $X\subseteq V(G)$, $X\neq \emptyset$ s.t. $G\setminus X$ has more than $|X|$ components, then $G$ has no Hamiltonian cycle. Proof. Suppose for a contradiction that $...
Sam Kirkiles's user avatar
  • 2,382
0 votes
1 answer
29 views

Bounds on shared edges between Hamiltonian cycles?

Smith theorem implies that the number of Hamiltonian cycles in cubic Hamiltonian graphs is at least two (It also implies that Hamiltonian cubic graphs contain at least three Hamiltonian cycles). Hence,...
Mohammad Al-Turkistany's user avatar
0 votes
1 answer
44 views

Some kind of general Ore theorem

I'm stuck in proving the following: If the Ore's condition for a graph is fulfilled (i.e. $\text{deg(u)+deg(v)}\geq n$ for all non-adjacent vertices u,v), one can prove the following: For increasingly ...
Bailey Hor's user avatar
1 vote
0 answers
27 views

What's the largest n such that any 3-connected graph of order n is hamiltonian?

I've figured out it's true for $n$ up to 6, using Ore's theorem. I'm not sure how to find an example of a non-hamiltonian 3-connected graph.
Joe Mansley's user avatar
0 votes
0 answers
119 views

Are all connected graphs with degree sequence $(2,2,4,4,6)$ Hamiltonian?

Are all connected graphs with degree sequence $(2,2,4,4,6)$ Hamiltonian? I have the following few observations: Note that there are only $5$ vertices but the highest degree is $6$. Hence the graph is ...
User8976's user avatar
  • 12.6k
3 votes
1 answer
174 views

Consider vertex $v$ in graph $G$. Let $v$ have at least three adjacent vertices with degrees of two. Prove that $G$ is not a Hamiltonian graph.

Consider vertex $v$ in graph $G$. Let $v$ have at least three adjacent vertices with degrees of two. Prove that $G$ is not a Hamiltonian graph. Proof Suppose $G$ is Hamiltonian. Let $x$, $y$ and $z$ ...
t-y's user avatar
  • 53
1 vote
1 answer
147 views

Intuition for Ore's theorem

Ore's theorem states that a graph $G$ is Hamiltonian if every disconnected pair of vertices $u, v \in G$ satisfy $\deg(u) + \deg(v) \geq |G|$. Is there an easy intuition for remembering this is true? ...
FountainTree's user avatar
1 vote
1 answer
63 views

Find a bound for the probability that a random simple graph with p = 1/2 + \alpha does not contain a Hamilton cycle

So I had a reasonable seeming solution using a Chernoff bound, but then realized I'd forgotten to add 1 when calculating my Delta and now my solution just seems off, any input would be welcome. Let Xi ...
Fregheit Meier's user avatar
3 votes
2 answers
110 views

Proving a graph does not have a hamilton path [closed]

I can see intuitively why this graph will not have a Hamilton path, but I can't seem to write up a convincing proof. Are there any tips on how to prove that a graph does not have a hamilton path?
Ray's user avatar
  • 77
1 vote
2 answers
127 views

Proving a graph does not have a hamilton circuit

Hello, I am trying to prove that this graph does not have a Hamilton circuit. The only thing I know is that all vertices of degree 2 must have all their edges in the circuit, however this does not ...
Ray's user avatar
  • 77
0 votes
1 answer
64 views

Prove that a graph is or isn't hamiltonian

Prove that graph is hamiltonian or if it isn't proof that it isn't. I tried everything from Ore to to Dirac. If I try to prove that it is not hamiltonian, then I can't find which vertices$\in S$ to ...
VLC's user avatar
  • 2,527
1 vote
1 answer
549 views

Peterson Graph Non-Hamiltonian Proof Explanation

I'm working on graph theory and I'm trying to find a generalised elegant proof to non-Hamiltonian graphs. I stumbled onto this proof from D. West, which is simple, but I'm having trouble understanding ...
Major Redux's user avatar
1 vote
0 answers
156 views

How to prove that the cartesian product of $2$ grid graphs $P_n$ and $P_q$ (where $n$ and $q$ are odd) is not hamiltonian?

Let us assume that we have the graph $G$ which is the cartesian product of two grid graphs $P_n$ and $P_q$ wherein $n$ and $q$ are odd, I need to prove that $G$ is never hamiltonian. I am able to ...
Shubharthi Dey's user avatar
2 votes
0 answers
111 views

Non hamiltonian cubic graphs

It is known that almost all cubic graphs are hamiltonian (see here) However, I did not find any information about non-hamiltonian cubic graphs online. If you know some properties/literature about non-...
MariyaKav's user avatar
  • 243
1 vote
1 answer
63 views

Questions about Hamiltonicity of random graphs.

I’m reading a proof on the Hamiltonicity of a random graph, and there’s a few details that I’m not clear about. Here’s the setup and argument: Let $G$ be a graph on $[n]$, $\alpha \in (0,1)$, and $R =...
ensbana's user avatar
  • 2,287
1 vote
1 answer
104 views

A multigraph $G$ has even no of Hamiltonian paths

Following Corollary is taken from : HAMILTONIAN CYCLES AND UNIQUELY EDGE COLOURABLE GRAPHS Definition (Stick) : A path $s= e_1,...,e_m$ in $G$,where the end vertices of the edge $e_i$ are $v_i$ and $...
False Equivalence's user avatar
1 vote
1 answer
43 views

T-Colouring of Hamiltonian Circuit in Cubic Graph

I am trying to understand this paper On Hamiltonian Circuits. I am unable to understand why the following is true : $ X( S_{1}) +X( S_{2}) +X( S_{3}) = 0.$ $\: (1)$ Here $X(S)$ is representing the $...
False Equivalence's user avatar
2 votes
1 answer
284 views

Regular, connected, bipartite graph with no Hamilton cycle

Find an example of a graph $G$ with 3 or more vertices that is regular, connected, bipartite, and contains no Hamilton cycle. Please give me a hint. What I've got so far: Since $G$ is regular and ...
Noppawee Apichonpongpan's user avatar
1 vote
1 answer
98 views

Reference Request : 3-regular graphs are not uniquely hamiltonian.

I have found the following articles which relates somewhat to what I am searching for but completely so I need help finding more references, if not similar to what I have then anything closely related ...
False Equivalence's user avatar
3 votes
3 answers
582 views

Difficulty in understanding the proof of Petersen Graph is non hamiltonian as given in graph theory text by Chartrand and Zhang

I was going through the text : A First Course in Graph Theory by Chartrand and Zhang where I could not understand a few statements in the proof. Below is the excerpt: Theorem 6.4 : Petersen graph is ...
Abhishek Ghosh's user avatar
2 votes
1 answer
44 views

Hamiltonicity in graphs of small diameter

Consider a graph of small diameter, say $O(1)$. Intuitively, it seems that such graphs have a much better chance of being Hamiltonian, since you must be able to "get around" the graph easily....
Plumpton's user avatar
  • 103
1 vote
0 answers
243 views

$\deg(v)+\deg(u)\geq n−1$, then $G$ contains a Hamiltonian Path. [duplicate]

If $G$ is a graph on $n$ vertices in which every pair of non-adjacent vertices $v$ and $u$ satisfy, $\deg(v) + \deg(u) \geq n − 1$, then $G$ contains a Hamiltonian Path. Attempt: Form a new graph $H$ ...
Gabriela's user avatar
  • 850
-1 votes
1 answer
116 views

Suppose you have a graph with 8 vertices, n greater than or equal to 4, that are colored red or blue

Suppose that the graph has exactly 14 edges. Prove that it contains a Hamilton Cycle. I thought of going in the direction of saying it is a bipartite graph which means since the amount of blue and red ...
Ali Muham's user avatar
0 votes
3 answers
215 views

Bridge in Hamilton graph

My task is to prove that Hamilton graph does not contain bridges(that is edge, and by removing that edge graph is disconnected). It is kind of obvious that by removing any edge from Hamilton contour ...
Trevor's user avatar
  • 533
2 votes
0 answers
72 views

The Hamiltonian cycle in a Cayley graph whose corresponding group has a finite cyclic normal subgroup [closed]

Let $S$ generate a finite group $G$ and $s \in S$ such that $\langle s\rangle \trianglelefteq G$, ${\rm Cay}(G/\langle s\rangle,S)$ has a Hamiltonian cycle. Let $(s_1,s_2, \cdots, s_n)$ be the ...
Hasini's user avatar
  • 201
0 votes
0 answers
37 views

Prove that a graph that has a Hamilton circuit [duplicate]

How can I prove this: Let $G$ be a simple graph with with $n\geq3$ vertices and $m$ edges. If $m\geq \frac12 (n^2 - 3n +6),$ then $G$ has a Hamilton circuit.
Raya 's user avatar
1 vote
1 answer
218 views

Ultra-Hamiltonian cycle

Ultra-Hamiltonian cycling is defined to be a closed walk that visits every vertex exactly once, except for at most one vertex that visits more than once. Question:- Prove that it is NP-hard to ...
Nitin Kumar Chauhan's user avatar
1 vote
1 answer
31 views

Sequence of elements representing a Hamiltonian cycle and the generating element of a subgroup

Let $S$ be a subset of a finite group $G$. The Cayley graph $Cay(G,S)$ can be defined as the graph whose vertices are the elements of $G$, with an edge joining $g$ and $gs$, for every $g \in G$ and $s ...
Buddhini Angelika's user avatar
1 vote
1 answer
680 views

prove that Petersen graph has no cycles less than or equal to 4 [duplicate]

I studying the proof that the Petersen graph is not Hamiltonian, and in the proof, they used an observation that seems intuitively correct but I want to provide rigorous proof for it, given that I'm ...
Mubarak Alsaeedi's user avatar
2 votes
1 answer
65 views

On existence of an hamiltonian path in cartesian power of directed cycle graph

Is it true, and if so, how to show it, that there is a Hamiltonian path in the cartesian power of a directed cycle graph (i.e. the iterated cartesian/box product $\square$) $C_n^{\square r}$ where $n, ...
Ignat Angelina's user avatar
2 votes
0 answers
58 views

Sufficient conditions for Hamilton paths

I have a conjecture about the Hamiltonian path, expressed as follows. Is it correct? For a connected graph $G$, if every vertex of $G$ is an end-vertex of some longest path of $G$, then $G$ has a ...
Wekii Liu's user avatar
3 votes
3 answers
388 views

How many Distinct Hamiltonian Maximal Planar Graphs are there (n vertices) and could this representation help?

If we make a regular polygon with n vertices (n edges) and triangulate on the inside with n-3 edges, then triangulate on the outside with (n-3) edges (or draw dotted lines inside again), a Maximal ...
John Hunter's user avatar
0 votes
1 answer
76 views

Let a graph $G$ have a cycle that contains a vertex covering of the graph. Prove that $L(G)$ is Hamiltonian

Suppose a graph $G$ have a cycle that contains a vertex covering of the graph. Prove that $L(G)$ is Hamiltonian
G' Prime's user avatar
2 votes
1 answer
43 views

Prove that if a graph $G$ has an independent vertex subset $X \subseteq V G$ such that $|X| > |N (X)|$ then $G$ is non-Hamiltonian.

Prove that if a graph $G$ has an independent vertex subset $X \subseteq V G$ such that $|X| > |N (X)|$ then $G$ is non-Hamiltonian. I have tried to delete m vertices in order to produce m component,...
G' Prime's user avatar
1 vote
2 answers
187 views

Are these graph Hamilton or not?

I have read it a lot about that but I am still confusing how to find out if it is Hamilton graph or not. I have check here some similar examples but I was not able to understand it. I know that a ...
ek.Sek's user avatar
  • 497