Star covers and star partitions of double-split graphs

Joyashree Mondal () and S. Vijayakumar ()
Additional contact information
Joyashree Mondal: Indian Institute of Information Technology, Design and Manufacturing (IIITDM), Kancheepuram
S. Vijayakumar: Indian Institute of Information Technology, Design and Manufacturing (IIITDM), Kancheepuram

Journal of Combinatorial Optimization, 2024, vol. 47, issue 3, No 2, 51 pages

Abstract: Abstract 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.

Keywords: Star cover; Star partition; Double-split graphs; Polynomial time algorithms; 05C85; 68Q25; 68R10 (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01112-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:3:d:10.1007_s10878-024-01112-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01112-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().