Questions tagged [hamiltonicity]

For questions related to the Hamiltonicity of a graph.

Filter by
Sorted by
Tagged with
3
votes
2answers
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 | <$ ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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-...
1
vote
1answer
53 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 =...
1
vote
1answer
48 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 $...
1
vote
1answer
30 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 $...
2
votes
1answer
85 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 ...
1
vote
1answer
36 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 ...
3
votes
3answers
152 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 ...
2
votes
1answer
33 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....
0
votes
0answers
16 views

Applications of Hamiltonian Decompositions

A Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. What are some applications of Hamiltonian decompositions? In what ways are they important ...
1
vote
0answers
66 views

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

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$ ...
0
votes
0answers
23 views

Relation of the product of elements in the quotient graph to two Hamiltonian cycles differing in one edge

Lemma: Let $G$ be a finite group and $S$ be a generating set of $G$. Suppose, $N$ is a cyclic normal subgroup of $G$ $(s_1N, \cdots , s_n N)$ is a Hamiltonian cycle in $Cay(G/N,S)$ the product $s_1 ...
-1
votes
1answer
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 ...
0
votes
3answers
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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$, ...
0
votes
0answers
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.
1
vote
1answer
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 ...
1
vote
1answer
26 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 ...
1
vote
1answer
140 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 ...
2
votes
1answer
53 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, ...
2
votes
0answers
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 ...
2
votes
3answers
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 ...
0
votes
1answer
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
2
votes
1answer
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,...
3
votes
3answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
101 views

Let $G$ be a simple graph with $n$ vertices not Hamiltonian such that $G+\{x_i,x_j\} $ is Hamiltonian.

Let $G=(X,U)$ be a simple graph, with $n$ vertices, not Hamiltonian and such that, for any distinct and non-adjacent $x_i$ and $x_j$ vertices, $G+\{x_i,x_j\} $ is Hamiltonian. I need to show that (i) $...
1
vote
1answer
85 views

Let $G$ be a simple regular graph of odd degree, with $n\geq 4$ vertices. Show that $G$ or its complementary graph $\overline{G}$ is hamiltonian.

Let $G$ be a simple regular graph of odd degree, with $n\geq 4$ vertices. Show that $G$ or its complementary graph $\overline{G}$ is hamiltonian. First, if we assume that $G$ is $r-$regular we obtain:...
0
votes
0answers
27 views

Show that this directed graph is eulerian and hamiltonian

Define the directed graph $D_{n,k} = (V_{n,k},A_{n,k})$ for $k \ge 2$. The vertices are the $k$-dimensional vectors with values between 1 and $n$, that is $V=\{1,..n \}^k$. Two vertices $u=(u_1,...,...
1
vote
0answers
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 ...
0
votes
2answers
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$...
0
votes
1answer
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 ...
3
votes
1answer
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 - ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
0
votes
2answers
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 ...
2
votes
1answer
144 views

Dirac's theroem for bipartite graphs

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 ...
1
vote
0answers
15 views

Finding the relationship between generating elements represented by a Hamiltonian cycle of a Cayley graph

Consider an undirected Cayley graph of a finite group $\mathbb{Z}_p \times \mathbb{Z}_q$, where $p$ and $q$ are distinct primes. Let the generating set for the Cayley graph be $S=\{g_p, g_q\}$, where $...
0
votes
0answers
28 views

Relationship between the generating elements given by the Hamiltonian cycle of a Cayley graph

Consider the Cayley graph of $\mathbb{Z}_3 \times \mathbb{Z}_5$ generated by the generating set $S=\{g_1=(1,0), g_2=(0,1)\}$. Then $|g_1|=3, |g_2|=5$. Consider a Hamiltonian cycle, $ABCDEFGHIKJLMNO$. ...
3
votes
2answers
139 views

Finding the inverse of line graphs L(G)

I just learned about line graphs $L(G)$ such that all vertices $v$ in $L(G)$ represent edges in $G$. Is there a way to find for any graph $G$, a graph $G'$ such that $G = L(G')$? The potential usage ...
1
vote
1answer
139 views

prove that the graph $G$ is hamiltonian

Problem: If $G$ is a graph with $m$ edges and $n\geq 3$ vertices, where $2m \geq n^{2} - 3n + 6$, prove that $G$ is a hamiltonian graph. (Hint: Consider the following theorem and corollary.) ...
3
votes
1answer
148 views

Example of locally Hamiltonian but not Hamiltonian graph.

Question. A graph is a locally Hamiltonian graph if for every vertex $v$ induced subgraph $G(N(v))$ is Hamiltonian. Give an example of a locally Hamiltonian but not Hamiltonian graph. Part of the ...
0
votes
1answer
43 views

Hamilton decompositions of cycle plus triangles graphs

A cycle plus triangles graph is a 4-regular graph $G$ with a Hamiltonian circuit $C$ and such that the chords of $C$ induce a set of disjoint triangles (3-circuits). A 4-regular graph $G$ has a ...