2
$\begingroup$

Definition A hamiltonian cycle is a cycle that visits each vertex exactly once. A graph that contains a hamiltonian cycle is called a hamiltonian graph.

Background Barnette's conjecture is a well known conjecture which deals with the hamiltonicity of 3-regular bipartite.

Question It appears that there is no conjecture that deals with the hamiltonicity of $d$-regular bipartite graphs when $d\geq 4$, my question is

Are all the connected 4-regular bipartite graphs are Hamiltonian? (or $d$-regular where $d\geq 4$)?

If not, is there any work that deals with the hamiltonicity of the connected $ d$-regular bipartite graphs for some $d\geq 4$. If yes, could you please point me to some references.

Any idea (or reference) will be useful!

$\endgroup$
1
  • $\begingroup$ @bof yes exactly, I edited the question. In fact, in order for the graph to be hamiltonian it should be connected. $\endgroup$
    – M.Badaoui
    Commented May 3, 2017 at 14:04

1 Answer 1

5
$\begingroup$

The Hamiltonian cycle problem (HCP) is NP-complete in the class of $2$-connected bipartite $d$-regular graphs for each $d \ge 3$.

Proof. It is known (see Akiyama, Nishizeki, Saito, NP-Completeness of the Hamiltonian Cycle Problem for Bipartite Graphs) that HCP is NP-complete in the class of $3$-connected bipartite cubic graphs (and therefore is NP-complete in the class of $2$-connected bipartite cubic graphs). And it is clear that HCP is in NP for any graph class. Let's show a polynomial reduction of HCP in the class of $2$-connected bipartite $d$-regular graphs to HCP in the class of $2$-connected bipartite $(d+1)$-regular graphs for $d \ge 3$.

Let $G$ be a $2$-connected bipartite $d$-regular graph. Let $G_1$ and $G_2$ be two copies of $G$. Now for each vertex $v$ of $G$ we take a copy $X_v$ of complete bipartite graph $K_{d+1, d+1}$, remove an edge between vertices $u_1$ and $u_2$ and then add edges $\{\,u_1, v_1\,\}$ and $\{\,u_2, v_2\,\}$, where $v_1$ and $v_2$ are copies of $v$ in $G_1$ and $G_2$ correspondingly. It is easy to see that constructed graph $H$ is bipartite and $(d + 1)$-regular. Graph $H$ is Hamiltonian if and only if $G$ is Hamiltonian.

Let $C$ be a Hamiltonian cycle in graph $G$. Then we replace each vertex $v$ with $v_1P_vv_2$ where $P_v$ is a Hamiltonian $(u_1, u_2)$-path in $X_v$. So we get a Hamiltonian cycle in $H$.

Let $C$ be a Hamiltonian cycle in graph $H$. Then for each $v$ all vertices of $X_v$ take consequtive $2d + 2$ positions between $v_1$ and $v_2$. If we replace each such part of cycle with $v$ we get a Hamiltonian cycle in $G$. $\square$

Therefore the answer to your question is no, no and again no, for each $d \ge 3$ there are infinitely many connected bipartite $d$-regular non-Hamiltonian graphs. However almost all regular bipartite graphs are Hamiltonian. Also non-Hamiltonian such graphs are not too small. Particularly it is conjectured by Häggkvist that every $2$-connected $k$-regular bipartite graph on at most $6k$ vertices is Hamiltonian. And it is proved that every $2$-connected $k$-regular bipartite graph on at most $6k - 38$ vertices is Hamiltonian.

$\endgroup$
1
  • $\begingroup$ Thank you for the beautiful and comprehensive answer ! $\endgroup$
    – M.Badaoui
    Commented May 4, 2017 at 10:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .