4
$\begingroup$

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 that if $G \in S$ is c-connected, it follows that $G$ is Hamiltonian? I know that if $c$ does exist, $c\geq 3$.

If possible, can we get values $c_d$ for induced subgraphs of d-dimensional rook graphs that are the product of $d$ complete graphs?

$\endgroup$
2
  • $\begingroup$ The rook graph (rook's moves on an $n\times n$ chessboard) is the cartesian product of complete graphs, not the direct product. $\endgroup$ Dec 5, 2019 at 0:35
  • $\begingroup$ @BrendanMcKay fixed, thanks $\endgroup$ Dec 5, 2019 at 0:35

1 Answer 1

4
$\begingroup$

It's known that $3\leq c \leq7$.

$S$ is the class of line graphs of bipartite graphs, by ISGCI.

The line graph of this graph is 2-connected and non-Hamiltonian, so $c\geq3$.

Siming Zhan proved that 7-connected line graphs are Hamiltonian, so $c\leq 7$. See Zhan, Siming. "On hamiltonian line graphs and connectivity." Discrete Mathematics 89.1 (1991): 89-95.

$\endgroup$
1
  • 1
    $\begingroup$ interesting! I wonder if this easily generalizes for $c_d$... $\endgroup$ Dec 5, 2019 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.