Questions tagged [hamiltonicity]

For questions related to the Hamiltonicity of a graph.

88 questions
Filter by
Sorted by
Tagged with
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 ...
• 93
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)?
• 1,939
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 ...
• 2,288
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 ...
• 2,288
1 vote
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 ...
• 415
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. ...
1 vote
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 ...
• 13
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 ...
• 2,288
1 vote
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-...
• 2,288
1 vote
66 views

• 2,382
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,...
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 ...
1 vote
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.
• 303
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 ...
• 12.6k
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$ ...
• 53
1 vote
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? ...
• 273
1 vote
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 ...
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?
• 77
1 vote
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 ...
• 77
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 ...
• 2,527
1 vote
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 ...
• 197
1 vote
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 ...
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-...
• 243
1 vote
63 views

1 vote
43 views

1 vote
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 ...
65 views

• 83
1 vote