Anzeige
Erschienen in:
01.04.2024
Star covers and star partitions of double-split graphs
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2024
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A graph that is isomorphic to the complete bipartite graph \(K_{1,r}\) for some \(r\ge 0\) is called a star. A collection \(\mathcal {C} = \{V_1, \ldots , V_k\}\) of subsets of the vertex set of a graph \(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\). A star cover \(\mathcal {C}\) of a graph \(G = (V, E)\) is called a star partition of G if \(\mathcal {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)\) time exact algorithms for double-split graphs. Proving that our algorithms indeed have running time \(\varOmega (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.