Hamiltonicity of bipartite graphs maximum degree $3$, where $X$ or $Y$ is a clique

Question

I'm quite new to graph theory and NP-complete proofs. I stumbled across NP-completeness on hamiltonicity of bipartite graphs with maximum degree $3$ and was wondering whether the same applies to graphs where one of the sets $X$ or $Y$ now additionally forms a clique. My thought process was, that these graphs remain NP-complete, even though their maximum degree is not $3$ anymore, since we would still transverse from $X$ to $Y$ and $Y$ to $X$ in order to have a Hamilton circuit pretty much ignoring the additional edges in $X$ or $Y$.

Maybe someone can shed some light on my question or forward me to something where I can read up on this.

Edit: If this was true this would also prove that Hamilton circuits are NP-complete in split graphs, right?

Answer 1

Yes, you conclusion and idea are correct, though proof is not so rigorous.

Given a bipartite graph $G$. For bipartite graphs we have a simple necessary condition of Hamiltonicity: parts should have the same cardinality. If parts have the same cardinalities, let's build a split graph $H$, pairwise connecting vertices of one part by an edge. If $G$ is Hamiltonian, then $H$ has the same Hamiltonian cycle and therefore is Hamiltonian. Note that vertices from one part of the graph $G$ are adjacent in the graph $H$ to the vertices from the other part only, and number of such vertices in both parts is the same. Therefore Hamiltonian cycle in graph $H$ doesn't contain edges that don't present in the graph $G$. Thus if $H$ is Hamiltonian, then $G$ has the same Hamiltonian cycle. So the graph $H$ is a split graph, and the graph $H$ is Hamiltonian if and only if the graph $G$ is Hamiltonian. Note that the number of vertices and edges in the graph $H$ is polynomial of the number of vertices and edges in the graph $G$.

Therefore we have a polynomial reduction from Hamiltonian cycle problem (HCP) for a bipartite graph to HCP for a split graph. Since in the class of bipartite graphs HCP is NP-complete and in any graph class HCP is in NP, then in the class of split graphs HCP is also NP-complete.