# Questions tagged [hamiltonian-graphs]

A Hamiltonian graph (directed or undirected) is a graph that contains a Hamiltonian cycle, that is, a cycle that visits every vertex exactly once.

62 questions
Filter by
Sorted by
Tagged with
120 views

### Is this case of Barnette's Conjecture known?

Context: Barnette's Conjecture is that every bipartite cubic polyhedral graph is Hamiltonian. I have been interested by this problem for a long time, and I recently came up with a result. From my ...
77 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 ...
31 views

### Are all cyclically 4-connected CUBIC graphs which have a chordless dominating circuit (MO graphs) Hamiltonian?

An MO graph is a simple cubic graph with a chordless dominating circuit (that is, a circuit which has no chords and which, if deleted, leaves behind a set of isolated vertices). In a previous post (...
77 views

### Does 2-connectivity imply Hamiltoniancy for subgraphs of the rook graph

We say the rook graph, $R_n$, is the cartesian product of $K_n \times K_n$. Let $S$ be the set of graphs that are an induced subgraph of $R_n$ for some $n$. Does there exist some constant $c$ such ...
93 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 ...
75 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 ...
59 views

### Normal colorings of bridgeless cubic graphs

Definition (informal) A normal edge-5-coloring of a bridgeless cubic graph $G$ is a proper 5 coloring of the edges of the graph, so that for each edge $e\in E(G)$, either $e$ and the four edges ...
430 views

### Arranging all permutations on $\{1,\ldots,n\}$ such that there are no common points

If $n>0$ is an integer, let $[n]=\{1,\ldots,n\}$. Let $S_n$ denote the set of all permutations (bijections) $\pi:[n]\to[n]$. For which positive integers $n$ is there a bijection $\Phi:[n!]\to S_n$ ...
120 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 ...
1k 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 ...
775 views

### Are all cubic graphs almost Hamiltonian?

Call a graph $G$ $n$-almost-Hamiltonian if there is a closed walk in $G$ that visits every vertex of $G$ exactly $n$-times. So a Hamiltonian graph is $n$-almost-Hamiltonian for all $n$. Are all ...
142 views

### Is there a permutation $\pi\in S_n$ with $\sum\limits_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0$ for each $n>7$?

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$. QUESTION: Is it true that for each $n=8,9,\ldots$ we have $$\sum_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0\tag{*}$$ for ...
179 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 ...
165 views

### What is the complexity of counting Hamiltonian cycles of a graph?

Since deciding whether a graph contains a Hamiltonian cycle is $NP$-complete, the counting problem which counts the number of such cycles of a graph is $NP$-hard. Is it also $PP$-hard in the sense ...
161 views

### Grinberg's uniquely hamiltonian 3-connected graphs (Russian paper)

Many years ago, Grinberg found some uniquely-hamiltonian $3$-connected graphs, and published his results in a paper that has been cited several times as follows. E. Grinberg, Three-connected graphs ...
117 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 ...
71 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 ...
134 views

### Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?

In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...
345 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 ...
40 views

### Maximal non-hamiltonian graphs - spanned by a theta graph?

At the moment I am interested in maximal non-hamiltonian graphs, so that is a (simple, undirected) graph that does not itself have a hamilton cycle, but if you add an edge between any two distinct non-...
101 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$ ...
84 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{ ...