Logo image
Back
The Algorithmic Complexity of k-Domatic Partition of Graphs
Book chapter   Open access   Peer reviewed

The Algorithmic Complexity of k-Domatic Partition of Graphs

Hongyu Liang
Theoretical Computer Science, pp 240-249
2012
DOI: https://doi.org/10.1007/978-3-642-33475-7_17
url
https://link.springer.com/content/pdf/10.1007/978-3-642-33475-7_17.pdfView
Published, Version of Record (VoR) Open

Abstract

Algorithmic Complexity Bipartite Graph Domination Number Polynomial Time Algorithm Sensor Network
Let G = (V,E) be a simple undirected graph, and k be a positive integer. A k-dominating set of G is a set of vertices S ⊆ V satisfying that every vertex in V ∖ S is adjacent to at least k vertices in S. A k-domatic partition of G is a partition of V into k-dominating sets. The k-domatic number of G is the maximum number of k-dominating sets contained in a k-domatic partition of G. In this paper we study the k-domatic number from both algorithmic complexity and graph theoretic points of view. We prove that it is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{NP}$\end{document}-complete to decide whether the k-domatic number of a bipartite graph is at least 3, and present a polynomial time algorithm that approximates the k-domatic number of a graph of order n within a factor of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac{1}{k}+o(1))\ln n$\end{document}, generalizing the (1 + o(1))ln n approximation for the 1-domatic number given in [5]. In addition, we determine the exact values of the k-domatic number of some particular classes of graphs.

Metrics

20 Record Views
3 citations in Scopus

Details

Logo image