Questions tagged [hamiltonicity]
For questions related to the Hamiltonicity of a graph.
92
questions
0
votes
0
answers
22
views
What is the toughness of Tutte graph?
Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte.
Let $c(G)$ denote the number of components of a graph $G$.
If $G$ is not complete, the toughness of $G$ $$\tau(G)...
- 2,474
1
vote
1
answer
62
views
Is colour smoothness equivalent to finding a cover via disjoint cycles?
Let $G$ be a finite bipartite graph, with colouring function $c \colon V(G) \to \{-1, 1\}$. I want to consider the problem of finding vertex-disjoint cycles whose union spans $G$. We have the ...
- 117
3
votes
1
answer
34
views
Hamiltonian graph on a $8\times 8$ chessboard with upper left corner and bottom right corner square removed
Suppose we are given the setup in the title. Two squares are adjacent if and only if they share a common edge. I want to find out whether the obtained graph considering squares as nodes would be ...
- 79
1
vote
1
answer
42
views
$G$ hamiltonian iff $H^2$ is hamiltonian
Let $G$ be a graph on the vertex set $V = \{v_0, \ldots, v_{n-1}\}$. Construct $H$ as the graph on vertex set $\{v_0, \ldots, v_{n-1}, u_0, \ldots, u_{n-1}, w_0, \ldots, w_{n-1}\}$ with
$$
E(H) = E(G) ...
- 511
0
votes
0
answers
31
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 ...
- 103
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)?
- 1,949
2
votes
0
answers
79
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,474
0
votes
1
answer
37
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,474
1
vote
1
answer
100
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
3
votes
1
answer
72
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. ...
- 71
1
vote
1
answer
35
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
4
votes
1
answer
115
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,474
1
vote
1
answer
94
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,474
1
vote
1
answer
67
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 $\...
- 663
0
votes
0
answers
145
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 ...
