Impact of Diameter and Convex Ordering for Hamiltonicity and Domination

A bipartite graph G(X, Y) is called a star convex bipartite graph with convexity on X if there is an associated star T on X such that for each vertex in Y, its neighborhood induces a subtree in T. A split graph G(K, I) is a graph that can be partitioned into a clique (K) and an independent set (I). The objective of this study is twofold: (i) to strengthen the results presented in [1] for the Hamiltonian cycle (HCYCLE), the Hamiltonian path (HPATH), and Domination (DS) problems on star convex bipartite graphs (ii) to reinforce the results of [2] for HCYCLE, and HPATH on split graphs by introducing convex ordering on one of the partitions (clique or independent set). We establish the following dichotomy results on star convex bipartite graphs: (i) HCYCLE is NP-complete for diameter 3, and polynomial-time solvable for diameter 2, 5, and 6 (ii) HPATH is polynomial-time solvable for diameter 2, and NP-Complete, otherwise. Note that HCYCLE and HPATH are NP-complete on star convex bipartite graphs with diameter 4 1. Similarly, we present the following results on split graphs by imposing convexity on K (I); HCYCLE and HPATH are NP-complete on star (comb) convex split graphs with convexity on K (I). On the positive side, we show that for \(K_{1,5}\) -free star convex split graphs with convexity on I, HCYCLE is polynomial-time solvable. We further show that the domination problem and its variants (Connected, Total, Outer-Connected, and Dominating biclique) are NP-complete on star convex bipartite graphs with diameter 3 (diameter 5, diameter 6). On the parameterized complexity front, we prove that the parameterized version of the domination problem, with the parameter being the solution size, is not fixed-parameter tractable on star convex bipartite graphs with a diameter at most 4, whereas it is fixed-parameter tractable when the parameter is the number of leaves in the associated star.