Questions tagged [hamiltonicity]

For questions related to the Hamiltonicity of a graph.

61 questions
Filter by
Sorted by
Tagged with
36 views

Graph theory - planar and hamiltonian graphs

Is the graph in the figure an Hamiltonian graph? Is the graph in the figure a planar graph? Attempt: I suspect that the graph is not Hamiltonian, because if we take ??? for the set $S$, $| S | <$ ...
48 views

planar and Hamiltonian graphs [closed]

Is the graph in the figure an Hamiltonian graph? Is the graph in the figure a planar graph? Attempt: Is it even possible to solve the first question using this theorem: "Let G be a graph and S an ...
56 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 ...
36 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 ...
41 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-...
53 views

30 views

81 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 ...
63 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 ...
39 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 ...
22 views

Hamiltonian cycles in a quotient graph and original graph

I am currently reading regarding Hamiltonian cycles and I came across the following. "Suppose, $N$ is a cyclic normal subgroup of $G$, such that $|N|$ is a prime power. $<s^{-1}t> = N$, ...
33 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.
110 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 ...
26 views

51 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 ...
328 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 ...
41 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
37 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,...
221 views

Using Bellman-Ford to find a Hamiltonian cycle? (NP-complete)

Let $G(V,E)$ be a directed graph, where $V=\{a_1,\ldots,a_n\}$ is a set of vertices and $E$ is a set of ordered pairs of $V$, with $|V|=n$. Now, let be $G(W,F)$ be a graph where $W$ is a set of ...
32 views

Prove that $G$ is Hamiltonian.Suppose that $𝑛$ $\geq$ $6$ $\delta$(𝐺) and |E(G)| $>$ $\binom {n - \delta (G)} {2}$ + $\delta^2(G)$

Suppose that $G$ is a simple graph with $n$ vertices such that $𝑛$ $\geq$ $6$ $\delta$(𝐺) and |E(G)| $>$ $\binom {n - \delta (G)} {2}$ + $\delta^2(G)$. Prove that $G$ is a Hamiltonian. . I know ...
112 views

What are the advantages of Hamiltonian paths/cycles in Cayley graphs when considering their applications

If a function (like a hash function) maps a vertex of a connected Cayley graph to another vertex which will be the ending point of a Hamiltonian path, is there a particular advantage over a function ...
101 views

31 views

Number of each generating elements of the Cayley graph appearing in a Hamiltonian cycle

Let $G$ be a finite group and $S$ be a subset of $G$. Let the Cayley graph of $G$ with respect to $S$ be $Cay(G,S)$, provided that $1 {\not\in} S$ and $S$ is inverse closed. Consider the Cayley graph ...
152 views

Hamiltonian cycle in complete bipartite graph

Let $\Gamma=(V,E)$ be a complete bipartite graph with bipartition $V=R\cup B$. Show that if $\Gamma$ is hamiltonian then $|R|=|B|$. My attempt: Suppose $\Gamma$ is hamiltonian. Put $|R|=m$ and $|B|=n$...
207 views

Suppose a classroom has 25 students seated in desks in a square 5 × 5 array.

The teacher wants to alter the seating by having every student move to an adjacent seat (just ahead, just behind, on the left, or on the right). Show that such a move is impossible. I just want to ...
337 views

"Tricky" questions on graph theory

So , I am revising graph theory. I need to gain some help/ feedback for those, because at least to me they are tricky. They are supposed to be answered quickly , because they come from a tight timed - ...
91 views

How many distinct graphs can be drawn and which of them are not hamiltonian?

Given the following template of a simple cubic bipartite graph: $\hskip1.7in$ Missing edges shall be drawn from the top nodes to the bottom nodes. No loops and multiedges allowed. How many distinct ...
38 views

Hamiltonian graph

Let $G$ be a graph with $n+k$ vertices such that $n$ vertices have degree at least $\frac{n+k}{2}$ and the remaining $k$ vertices have degree at least $k+1$. Show that G is Hamiltonian. Using Diracs ...
111 views

Prove that if a graph is Hamiltonian then after removing k vertices, number of its connected components increases to no more than k.

I thought maybe induction? But components of a graph after removing k vertices aren't Hamiltonian and I'm not sure how to justify that removing one more vertix won't increase number of components by ...
53 views

Knight on a $3\times 4$ board: Hamiltonian graphs

A chess knight sits on a $3\times 4$ board. Is it possible for the knight to jump into the $12$ squares without jumping twice in any of them and ending and starting in the same box? What if it starts ...
57 views

Prove that G is Hamiltonian

Given $G$ a graph with degrees:$6,6,4,4,4,k,k$ on $7$ vertices and $10$ regions (and by Euler $n-f+r=2$ I found that $k$=3) prove $G$ is contains a Hamiltonian cycle I did find a visual cycle on the ...
The theorem of Dirac that any graph $G$ on $n\geq 3$ vertices with minimum degree $\delta(G)≥n/2$ contains a Hamilton cycle is one of the classical results of graph theory. Is there are analogous ...