Tree Convex Bipartite Graphs: NP-Complete Domination, Hamiltonicity and Treewidth

There are seven graph problems grouped into three classes of domination, Hamiltonicity and treewidth, which are known to be \(\mathcal{NP}\)-complete for bipartite graphs, but tractable for convex bipartite graphs. We show these problems to remain \(\mathcal{NP}\)-complete for tree convex bipartite graphs, even when the associated trees are stars or combs respectively. Tree convex bipartite graphs generalize convex bipartite graphs by associating a tree, instead of a path, on one set of the vertices, such that for every vertex in another set, the neighborhood of this vertex is a subtree.