All Questions
Tagged with hamiltonian-graphs graph-theory
102 questions
4
votes
0
answers
258
views
When is an induced subgraph of a Johnson graph hamilton-connected?
The Johnson graph $J(n,k)$ has as its vertices the $k$-subsets of $\{1, 2, \dots, n\}$ where two vertices are adjacent iff their intersection has size $k-1$. A graph is Hamilton-connected if every two ...
- 393
3
votes
2
answers
123
views
Number Associated with Straight-line Drawings of Hamiltonian Graphs
Is there anything known about the maximum number of simple-polygonal Hamilton cycles that a straight-line drawing of a Hamiltonian graph can have?
Put differently, if the vertices of a Hamilton ...
- 13.2k
3
votes
1
answer
138
views
Edge colorability and Hamiltonicity of certain classes of cubic graphs (MO graphs)
Let $G$ be a simple cubic graph (that is, 3-regular). A dominating circuit of $G$ is a circuit $C$ such that each edge of $G$ has an endvertex in $C$. The circuit $C$ is chordless if no edge which is ...
- 1,018
3
votes
1
answer
104
views
Edge coloring of a graph on alternating groups
Let $G$ be the Cayley graph on the alternating group $A_n\,n\ge4$ with generating set $$S=\begin{cases}\{(1,2,3),(1,3,2),\\(1,2,\ldots,n),(1,n,n-1,\ldots,2)\}, &n\ \text{odd}\\ \{(1,2,3),(1,3,2),\\...
- 2,089
3
votes
1
answer
266
views
What is the densest bipartite graph with unique Hamiltonian cycle?
In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices.
Analogously, what is the ...
- 13.9k
3
votes
2
answers
725
views
The perfect matching problem of planar graph
We know that connectivity is closely related to the Hamiltonian of planar graphs.
The most famous result is the Tutte theorem.
Theorem (Tutte, 1956). A 4-connected planar graph has a Hamiltonian ...
- 1,851
3
votes
1
answer
234
views
Counting cycle vertex covers on hypercube
Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle ...
- 3,979
3
votes
1
answer
117
views
Hamiltonicity of random graphs with high girth
We say that $G\sim G_{n,f}$ (for $f=f(n)$) if $G$ is chosen uniformly at random from all graphs on $n$ vertices with girth $g(G)\ge f(n)$. Is there any threshold function $F(n)$ such that when $f\ll F$...
- 221
3
votes
1
answer
219
views
Regular graphs with $a$ and $b$ Hamiltonian edges
Special case of this question.
Let $G$ be $r$-regular Hamiltonian graph.
An $a$ edge is an edge which is on every Hamiltonian cycle.
A $b$ edge is an edge which is on no Hamiltonian cycle.
$a(G)$ ...
- 25.4k
3
votes
0
answers
70
views
Hamilton cycles in Cayley graphs: between Rapaport-Strasser and Fleischner
A well-known question of Rapaport-Strasser asks whether every finite connected Cayley graph has a Hamilton cycle. Fleischner's Theorem implies that if $S$ is the generating set of such a Cayley graph $...
- 1,936
3
votes
0
answers
108
views
Hamiltonian path in $\{0,1\}^n$ with rotations and bit-flip in position 0
We consider any non-negative integer as an ordinal, that is $0=\emptyset$ and $n=\{0,\ldots,n-1\}$ for every positive integer. Let $\{0,1\}^n$ denote the set of $\{0,1\}$-vectors of length $n$.
Define ...
- 48.9k
3
votes
0
answers
76
views
Hamiltonian cycles in Cayley graph on alternating group
Let $G=\operatorname{Cay}(A_n,S)$ be the Cayley graph on the Alternating group $A_n\quad n\ge4$ with generating set $S=\{(1,2,3),(1,2,4),\ldots,(1,4,2),(1,3,2)\}$. One Hamiltonian cycle in $G$ for $n=...
- 2,089
3
votes
0
answers
107
views
Reference request: Bipartite symmetric graphs are hamiltonian
Does anyone know whether bipartite symmetric graphs are hamiltonian?
I'm not sure whether anyone have proved it before, but a nonhamiltonian symmetric bipartite graph would lead to a counterexample to ...
- 9,501
3
votes
0
answers
145
views
Hamiltonian cycle polytope for the hypercube graph
Let $Q_n$ denote the $n$ dimensional hypercube graph (i.e., graph formed from the vertices and edges of an n-dimensional hypercube). Denote the set of edges and vertices of $Q_n$ by $E_n$ and $V_n$ ...
- 393
3
votes
0
answers
129
views
Effect of removing a Hamiltonian cycle on the Laplacian spectrum
Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$).
Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$.
...
- 6,962
2
votes
2
answers
64
views
Does $(\omega, E)$ with the cycle condition have an $\omega$-path?
Let $G = (V,E)$ be a simple, undirected graph. We say that $v\neq w\in V$ lie on a common cycle if there is an integer $n\geq 3$ and an injective graph homomorphism $f: C_n\to V$ such that $v,w\in \...
- 48.9k
2
votes
1
answer
106
views
Hamiltonian path in divisibility graph
Let $\mathbb{N}$ denote the set of positive integers, and consider the graph $(\mathbb{N}, E)$ where a set $\{a,b\}$ of two distinct positive integers belongs to $E$ if there is an integer $k>1$ ...
- 48.9k
2
votes
1
answer
495
views
Is every $k$-edge connected $k$-regular graph Hamiltonian?
A graph $G$ is Hamiltonian if there is a Hamiltonian cycle in $G$.
Suppose $G$ is a $k$-edge connected $k$-regular graph with $k>1$.
Does this ensure that $G$ is Hamiltonian?
If not, how about ...
- 191
2
votes
1
answer
85
views
The number of Hamiltonian circuits on a convex polytope embedded in $\mathbb{R}^N$
Recently I wondered whether there might be a natural topological complexity measure for convex polytopes embedded in $\mathbb{R}^N$. After some reflection it occurred to me that the number of distinct ...
- 3,871
2
votes
2
answers
234
views
Decompose complete directed graph with n vertices into n edge-disjoint cycles with length n−1
I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in Bermond and Faber - Decomposition of the ...
- 21
2
votes
1
answer
606
views
Simple decomposition of $K_{2n}-I$ into hamiltonian cycles
http://mathworld.wolfram.com/HamiltonDecomposition.html
In the 1890s, Walecki showed that complete graphs K_n admit a Hamilton decomposition for odd n, and decompositions into Hamiltonian cycles ...
- 400
2
votes
1
answer
138
views
Two ears polygon in a maximal planar hamiltonian graph
Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to ...
- 35
2
votes
1
answer
298
views
Opposite-nearest neighbor algorithm vs. nearest neighbor algorithm
Take the traveling salesman problem, but with three slight twists:
You can choose a different start vertex for each of the two algorithms.
Each path from one vertex to another is of unique, arbitrary ...
- 21
2
votes
1
answer
321
views
Extending perfect matchings into Hamiltonian cycles
Let $G$ be a simple cubic graph which has a Hamiltonian circuit $C$. In general, it is not possible to find a second Hamiltonian circuit which contains all the chords of $C$. For example, the Wagner ...
- 1,018
2
votes
0
answers
112
views
Constructing Hamiltonian circuits in acyclic digraphs
Any directed graph $G$ lacking cycles can acquire a Hamiltonian circuit through the addition of a sufficient number of edges.
Q. Is there a method to minimize the addition of edges to achieve a ...
- 4,058
2
votes
0
answers
116
views
Two more counterexamples to a conjecture from 1975 about hamiltonicity of digraphs
Question from 2013
gives one counterexample to Nash-Williams's conjecture 1975 about hamiltonicity
of dense digraphs.
In the linked answer, @LouisD "reverse engineered" the counterexample
...
- 25.4k
2
votes
0
answers
184
views
Details about Kelman's equivalent form of Barnette's conjecture
Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles.
Kelman claims that this conjecture is equivalent to a stronger one, which imposes some ...
- 1,005
1
vote
2
answers
321
views
Hamiltonicity and minimal degree in bipartite graphs
Given an integer $k>1$, is there a connected bipartite graph $\Gamma = (A, B, E)$ where $A\cap B = \emptyset$ and $E \subseteq \big\{\{a, b\}:a\in A, b\in B\big\}$ such that
$|A| = |B|$,
$\text{...
- 48.9k
1
vote
3
answers
883
views
Hamiltonian paths in bipartite graphs with 2 sets of "almost" same cardinality
Suppose we have two finite disjoint sets $A, B \neq \emptyset$ such that $|A|$ and $|B|$ differ by at most $1$, and let $\Gamma = (A\cup B, E)$ where $E\subseteq \big\{\{a,b\}: a\in A, b\in B\big\}$ ...
- 48.9k
1
vote
2
answers
186
views
Hamiltonian cycle in $S_n$ with transpositions
For any set $X$, let $[X]^2=\{\{a,b\}:a\neq b \in X\}$. If $n\in\mathbb{N}$ is a positive integer, let $S_n$ denote the collection of bijections $\varphi:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$. Let $E_n\...
- 48.9k
1
vote
2
answers
603
views
Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity
While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of ...
- 2,993
1
vote
1
answer
120
views
How to construct a hamilton-connected cubic graph? Is it possible?
If we are given a large integer $k$, can we construct a hamiltonian-connected $n$-vertex graph for every even $n\geq k$ such that all its vertices are of degree 3? Is there any reference concerning ...
- 1,190
1
vote
3
answers
6k
views
Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?
I am not expertise in graph theory. So have to ask this question here. The term "good" means that the algorithms should be efficient for general undirected simple connected graphs with a higher ...
- 475
1
vote
1
answer
100
views
Is there a monograph or review of Hamiltonian cycles of graphs (or long cycles of graphs)？
In graph theory, a Hamiltonian cycle is a cycle that visits each vertex exactly once. Hamiltonian cycle has a long history, and I have followed some articles.
We can find plenty of examples of ...
- 1,851
1
vote
1
answer
178
views
Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?
Let $G$ be connected simple graph.
Clique cover of graph $G$ is partition of the vertices of $G$
into $k$ disjoint cliques $D'_i$.
Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle
in ...
- 25.4k
1
vote
1
answer
92
views
Existence of a strongly regular vertex ordering on cubic graphs
Definition: Let $G=(V,E)$ be a cubic (i.e. $3$-regular) graph, and $<$ a total order on $V$. For $v\in V$ let $v^\downarrow$ denote the set of nodes $w\in V$ such that $w<v$, and let $\alpha(v) =...
- 191
1
vote
1
answer
78
views
Graph gadget related to uniquely hamiltionian regular graphs (question #2)
Related to uniquely hamiltionian graphs.
For natural numbers $a,b$ define $(a,b)$ gadget $G$:
$G$ is finite simple graph. Two vertices $u,v$ are of degree $b$
and the rest of the vertices are of ...
- 25.4k
1
vote
0
answers
65
views
Has there been progress on Hamiltonicity in 4-connected claw-free graphs with a constant maximum degree?
In 1984, Matthews and Sumner [1] conjectured that every 4-connected claw-free graph is Hamiltonian, and this conjecture is still wide open.
I would like to know if there has been any progress on this ...
- 1,851
1
vote
0
answers
93
views
15-game graph contains a Hamiltonian path ? Lovász conjecture for groupoids, loops, quasigroups , etc?
Typically Cayley graphs are defined for groups and generators sets S. But basically one only needs some set S and another set V and partially defined operation SxV->V, then one defines graph with ...
- 24.9k
1
vote
0
answers
61
views
A generalized/set hamiltonian cycle problem on directed graphs
So this problem originally stems from the asymmetric generalized/set TSP problem, where I am interested in asking the question which or how many edges I can delete while maintaining feasability. The ...
- 111
1
vote
0
answers
147
views
Properties of graphs with Hankel-like adjacency matrix
I am having undirected graphs with adjacency matrices which have a regular Hankel-like form, e.g.,
$$A=\begin{pmatrix}0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & (6\times 0 \text{ ...
- 243
0
votes
1
answer
149
views
degG(x) + degG(y) >= n, show that the graph is hamiltonian [closed]
I'm trying to show that a connected graph which has order >=3, and having the following inequality is Hamiltonian:
...
- 3
0
votes
1
answer
1k
views
Does this graph contain at least two Hamiltonian cycles?
Let $G$ be a simple graph which is a $2n$-cycle together with $n$ chords such that $G$ is $3$-regular. In other words, the set of $n$ chords is a perfect matching of $G$.
I conjecture that for every ...
- 421
0
votes
0
answers
86
views
Uniqueness of compatible cycle decomposition for Eulerian trail
Fleischner mentions in his article Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs about the uniqueness of compatible cycle decomposition that ...
0
votes
0
answers
36
views
A class of directed graph, when their minimal polynomial of the adjacency matrix matches the characteristic polynomial
We consider an unweighted directed simple graph, $G$, with a Hamiltonian cycle.
Q. Assume that the adjacency matrix of $G$ is non-singular. Do the characteristic and minimal polynomials of the ...
- 4,058
0
votes
0
answers
52
views
Are there 4-connected planar non-hamilton multi-graphs?
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 ...
- 1,851
0
votes
0
answers
62
views
Clique sizes of generalized Kneser graphs
Are there known bounds for clique size in generalized Kneser graphs $KG(n,k,t)=K(n,k,t-1)$, the graph formed by distinct $k$ subsets of $n$ set so that two subsets with at most $t$ elements in common ...
- 2,089
0
votes
0
answers
65
views
Cycles in Kneser graphs with three vertices forming triangles
Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form ...
- 2,089
0
votes
0
answers
125
views
Are there any necessary conditions of the existence of a Hamiltonian cycle on directed graphs
I'm trying to prove that one concrete directed graph has no Hamiltonian cycle, but didn't seem to find any relevant theorems
0
votes
0
answers
64
views
Degree-constraints for the existence of vertex-disjoint directed cycle covers in digraphs
Given a digraph $G(E,V): (u,v)\in E\implies(v,u)\notin E$, what is known about lower bounds on the indegree and outdegree of the vertices that guarantee the existence of a vertex-disjoint directed ...
- 13.2k