Star covers and star partitions of double-split graphs

A graph that is isomorphic to the complete bipartite graph $$K_{1,r}$$ K 1 , r for some $$r\ge 0$$ r ≥ 0 is called a star. A collection $$\mathcal {C} = \{V_1, \ldots , V_k\}$$ C = { V 1 , … , V k } of subsets of the vertex set of a graph $$G = (V, E)$$ G = ( V , E ) is called a star cover of G if each set in the collection induces a star and has $$V_1\cup \ldots \cup V_k = V$$ V 1 ∪ … ∪ V k = V . A star cover $$\mathcal {C}$$ C of a graph $$G = (V, E)$$ G = ( V , E ) is called a star partition of G if $$\mathcal {C}$$ C is also a partition of V. The problem Star Cover takes a graph G as input and asks for a star cover of G of minimum size. The problem Star Partition takes a graph G as input and asks for a star partition of G of minimum size. From Shalu et al. (Discrete Appl Math 319:81–91, 2022), it follows that both these problems are NP-hard even for bipartite graphs. In this paper, we show that both Star Cover and Star Partition have $$O(n^7)$$ O ( n 7 ) time exact algorithms for double-split graphs. Proving that our algorithms indeed have running time $$\varOmega (n^7)$$ Ω ( n 7 ) necessitates the construction of an intricate infinite family of double-split graphs meeting several requirements. Other contributions of the paper are a simple linear time recognition algorithm for double-split graphs and a useful succinct matrix representation for double-split graphs.