3
$\begingroup$

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 densest bipartite graph with unique Hamiltonian cycle?

$\endgroup$
2
  • $\begingroup$ 1) I Think you are missing "unique" before perfect matching. 2) Why only the interest in bipartite graphs? Is something already known for general/nonbipartite graphs? $\endgroup$ Commented May 2, 2016 at 23:28
  • $\begingroup$ @JohnMachacek I feel bipartite case should be easy. $\endgroup$
    – Turbo
    Commented May 3, 2016 at 6:26

1 Answer 1

4
$\begingroup$

The OP asks for the densest bipartite graph having a exactly one Hamiltonian cycle. We remark that in Graphs with exactly one Hamiltonian cycle, John Sheehan shows that a graph on $n$ vertices with exactly one Hamiltonian cycle can have at most $\lfloor n^2/4\rfloor + 1$ edges and exhibits a graph $H_n$ achieving this bound. Furthermore the author states $H_n$ in the only graph achieving this bound. We will answer the OP's question by "bipartizing" the argument and construction of Sheehan.

Observe that a bipartite graph with a Hamiltonian cycle must have an even number of vertices. Let $G$ be a graph with vertices $\{x_i: 1 \leq 2n\}$ labeled so that $C = x_1x_2\cdots x_{2n}$ is the unique Hamiltonian cycle of $G$. Every edge of $G$ can be regarded as a chord of $C$. We let $C(G;l)$ denote the set of chords in $G$ of length $l$. So, elements of $C(G; l)$ will look like $x_ix_{i+l}$ with incides taken modulo $2n$. If $l > 1$ and $x_i x_{i+l}$ is a chord of $G$, then $x_{i+1} x_{i+l+1}$ cannot be a chord of $G$ otherwise $G$ would have more than one Hamiltonian cycle. This implies $|C(G;l)| \leq n$ for $l > 1$. In fact we can say $|C(G;2l-1)| < n$ for $l > 1$ because if $|C(G;2l-1)| = n$, then $G$ would contain a Hamiltonian cubic subgraph and hence at least three Hamiltonian cycles. Also, we see $|C(G,n)| < n/2$. So far, this is Sheehans's argument. Using the assumption that $G$ is bipartite we see that $|C(G; 2l)| = 0$ for $l > 0$.

Let $m$ denote the number of edges of $G$. We compute and see $$m = \sum_{l=1}^n |C(G;l)| \leq n(n+1)/2 + 1.$$

Consider the bipartite graph $G_{2n}$ with vertices $\{x_i : 1 \leq i \leq 2n\}$ and edges $$\{x_i x_{i+1} : 1 \leq i \leq 2n\} \cup \{x_{2i-1}x_{2j} : 2i < 2j < 2n, \; 1 \leq i < n-2\}.$$ Then $G_{2n}$ has $2n$ vertices, $n(n+1)/2 + 1$ edges, and a unique Hamiltonian cycle $C = x_1x_2 \cdots x_{2n}$. We remark graph $G_{2n}$ can be obtained from Sheehan's $H_{2n}$ by deleting the "non-bipartite" edges.

$\endgroup$
3
  • $\begingroup$ What is the densest bipartite graph with unique Perfect matching? $\endgroup$
    – Turbo
    Commented Feb 21, 2021 at 11:44
  • $\begingroup$ @1.. there was a question I actuallt answered on this. I found the link: mathoverflow.net/questions/226583/… $\endgroup$ Commented Feb 22, 2021 at 18:28
  • $\begingroup$ I am asking connected bipartite graphs. $\endgroup$
    – Turbo
    Commented Feb 26, 2021 at 3:30

You must log in to answer this question.

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