All Questions
40 questions
4
votes
0
answers
69
views
is a 4-connected planar graph still Hamiltonian after removing an edge?
We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
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 ...
5
votes
2
answers
191
views
Number of Hamiltonian cycles on 24-cell graph
I asked Wolfram Alpha for the number of Hamiltonian cycles on the 24-cell graph.
https://www.wolframalpha.com/input?i=number+of+hamiltonian+cycles+on+24-cell+graph
It answers 114.9 billion but doesn't ...
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 ...
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 ...
5
votes
0
answers
127
views
Do uniquely Hamiltonian graphs have cycles of a sufficiently long length?
Let C be a Hamiltonian cycle of a graph G.
Call an edge e of G a chord if e∉C.
Let each edge of C be weighted 1 and each chord be weighted 2.
The weight of a path or cycle of ...
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∈V let v↓ denote the set of nodes w∈V such that w<v, and let $\alpha(v) =...
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
votes
0
answers
234
views
How many 20-vertex 2-connected 5-regular non-Hamiltonian graphs are there?
As for the question in title, I attempted to use nauty to obtain them, but it has been running on my computer for nearly three days without producing any results.
<...
3
votes
1
answer
104
views
Edge coloring of a graph on alternating groups
Let G be the Cayley graph on the alternating group Ann≥4 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
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 ...
9
votes
2
answers
2k
views
Is this graph Hamiltonian?
Let G be a simple 2-connected graph with m+n vertices (n>m≥3) with degree sequence (m−1)m, (n−1)n; that is, G is degree-equivalent to two disjoint cliques Km, Kn of ...
6
votes
0
answers
164
views
Hamilton cycles in random graphs with just enough connectivity
What is the asymptotic probability that G has a Hamilton cycle if G is a random n vertex 43n edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
3
votes
0
answers
76
views
Hamiltonian cycles in Cayley graph on alternating group
Let G=Cay(An,S) be the Cayley graph on the Alternating group Ann≥4 with generating set S={(1,2,3),(1,2,4),…,(1,4,2),(1,3,2)}. One Hamiltonian cycle in G for $n=...
5
votes
0
answers
154
views
How to construct 4-regular graphs with few Hamiltonian decompositions?
A Hamiltonian decomposition of a finite simple graph is a partition of its edge set so that each partition class forms a Hamiltonian cycle. This is only possible if the graph is 2k-regular.
...
5
votes
1
answer
279
views
Infinitely many counterexamples to Nash-Williams's conjecture about hamiltonicity?
Question from 2013
gives one counterexample to Nash-Williams's conjecture about hamiltonicity
of dense digraphs.
Later, we found tens of counterexamples on more than 30 vertices
and believe there are ...
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
...
2
votes
1
answer
85
views
The number of Hamiltonian circuits on a convex polytope embedded in RN
Recently I wondered whether there might be a natural topological complexity measure for convex polytopes embedded in RN. After some reflection it occurred to me that the number of distinct ...
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
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 ...
12
votes
1
answer
424
views
Quantitatively characterizing the failure of the converse of Dirac's theorem
First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.
I am currently in a combinatorics and graph theory class and recently we have ...
4
votes
0
answers
143
views
Halin Graphs with Highest Number of Hamilton Cycles
Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles ...
9
votes
1
answer
399
views
Are bipartite Moore graphs Hamiltonian?
This is motivated by a computer-generated conjecture that bipartite distance-regular graphs are hamiltonian. I decided to check the case of Moore graphs first.
The cycles and complete bipartite graphs ...
9
votes
2
answers
2k
views
"Gray code" of all permutations
Informally asking, can we step through all permutations of the set {1,…,n} by just using transpositions?
More formally: For any n∈N let [n]={1,…,n} and let Sn be ...
3
votes
1
answer
234
views
Counting cycle vertex covers on hypercube
Let Qn be the n-dimensional hypercube graph. How many vertex cycle covers exist on Qn? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle ...
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 ...
5
votes
0
answers
99
views
Graph gadget related to uniquely hamiltionian regular graphs
A graph is uniquely hamiltonian if it has exactly one hamiltonian cycle.
According to a conjecture there are no r-regular uniquely hamiltonian
graphs for r>2 and of special interest is the ...
6
votes
0
answers
76
views
Cage graphs and even cycles
Let G be a (ν,g)-cage graph of degree ν with girth g and n=n(ν,g) vertices.
Based on the known examples, I am wondering if the following can be proved/disproved:
Is it true that ...
15
votes
2
answers
2k
views
What is the smallest uniquely hamiltonian graph with minimum degree at least 3?
I would like to know more about uniquely hamiltonian graphs with minimum vertex degree at least 3, and in particular what is the smallest one.
(Recall that a graph is hamiltonian if it has a cycle ...
11
votes
1
answer
328
views
How many edges can be added to two circles before the graph becomes Hamiltonian?
Start with two n-circles (v1⋯vn) and (w1⋯wn) of vertice sets V and W, where n≥5. Add a number of vertex-disjoint edges between V and W (thus no chords) in a way ...
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 n2 edges, if graph has 2n vertices.
Analogously, what is the ...
7
votes
1
answer
736
views
Refinement of Dirac's theorem on Hamiltonian graphs
Dirac's theorem states that if degree of each vertex of a graph G=(V,E) is not less than |V|/2, then it has Hamiltonian cycle. It is less known, but still known and not so hard to prove (though I ...
4
votes
2
answers
349
views
Can we find 3 disjoint directed Hamiltonian cycles in the cube?
Let D be the digraph on 2d vertices with d2d edges that we obtain by directing each edge of the d-dimensional hypercube in both directions.
Can we partition the edges of D into d ...
5
votes
1
answer
1k
views
How many hamiltonian cycles can be removed from a complete directed graph before it becomes disconnected?
The question started from a problem brought home by a friend's 5th grader: "How many ways can you seat 5 people around a round table so that the people sitting to the left of any person is different ...
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,…,n} where two vertices are adjacent iff their intersection has size k−1. A graph is Hamilton-connected if every two ...
6
votes
1
answer
243
views
Hamiltonicity criteria for sparse graphs
Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course).
There are three main classes of criteria for Hamiltonicity that I am aware of:
Dirac-...
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) ...
10
votes
2
answers
782
views
Graphs with many edges avoided by Hamiltonian cycles
Let G be a 3-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of G. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...
5
votes
1
answer
224
views
Reconstructing the number of Hamiltonian cycles
As is common terminology in graph reconstruction, given a graph G, we call a vertex deleted subgraph of G, a card, and call the multiset of all cards, the deck of G. The graph reconstruction ...
12
votes
1
answer
2k
views
Hobbled rook tour – Hamiltonian cycle on square grid
Consider a square grid of even side length (2n×2n). It is easy to see that there must exist a Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balanced if the number ...