Book chapter
The Algorithmic Complexity of k-Domatic Partition of Graphs
Theoretical Computer Science, pp 240-249
2012
Abstract
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
19 Record Views
3 citations in Scopus
Details
- Title
- The Algorithmic Complexity of k-Domatic Partition of Graphs
- Creators
- Hongyu Liang - Tsinghua University
- Publication Details
- Theoretical Computer Science, pp 240-249
- Series
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Resource Type
- Book chapter
- Language
- English
- Academic Unit
- School of Biomedical Engineering, Science, and Health Systems
- Scopus ID
- 2-s2.0-84866886312
- Other Identifier
- 991019320710904721