The Domatic Partition Problem in Separable Graphs

Mercedes Landete and José Luis Sainz-Pardo
Additional contact information
Mercedes Landete: Centro de Investigación Operativa, Universidad Miguel Hernández de Elche, 03202 Elche, Spain
José Luis Sainz-Pardo: Centro de Investigación Operativa, Universidad Miguel Hernández de Elche, 03202 Elche, Spain

Mathematics, 2022, vol. 10, issue 4, 1-19

Abstract: The domatic partition problem consists of partitioning a given graph into a maximum number of disjoint dominating sets. This problem is related with the domatic number problem, which consists of quantifying this maximum number of disjoint dominating sets. Both problems were proved to be NP-complete. In this paper, we present a decomposition algorithm for finding a domatic partition on separable graphs, that is, on graphs with blocks, and as a consequence, its domatic number, highly reducing the computational complexity. Computational results illustrate the benefits of the block decomposition algorithm.

Keywords: domatic partition; domatic number; decomposition algorithm; integer linear problem; graphs with blocks (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/4/640/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/4/640/ (text/html)

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:gam:jmathe:v:10:y:2022:i:4:p:640-:d:753125

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().