The domatic number problem
From MaRDI portal
A dominating set of a graph \(G=(V,E)\) is a subset \(D\) of \(V\) such that every vertex not in \(D\) is adjacent to some vertex in \(D\). The domatic number of \(G\) is the maximum positive integer \(k\) such that \(V\) can be partioned into \(k\) pairwise disjoint dominating sets. It was proved that the problem of determining the domatic number of a graph is NP-complete for general graphs. This paper investigates the domatic number of graphs which are obtained from small graphs by performing graph operations, such as union, join and the Cartesian product.
Recommendations
Cites work
- R -Domination in Graphs
- A linear algorithm for the domination number of a tree
- Domatically cocritical graphs
- Dominating sets and domatic number of circular arc graphs
- Domination, independent domination, and duality in strongly chordal graphs
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- scientific article; zbMATH DE number 3843803 (Why is no real title available?)
- scientific article; zbMATH DE number 3815677 (Why is no real title available?)
- scientific article; zbMATH DE number 3977044 (Why is no real title available?)
- scientific article; zbMATH DE number 3663191 (Why is no real title available?)
- scientific article; zbMATH DE number 3739597 (Why is no real title available?)
- scientific article; zbMATH DE number 3747181 (Why is no real title available?)
- scientific article; zbMATH DE number 3765843 (Why is no real title available?)
- scientific article; zbMATH DE number 140475 (Why is no real title available?)
- scientific article; zbMATH DE number 3596896 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3358515 (Why is no real title available?)
- On the domatic number of interval graphs
- Regular totally domatically full graphs
- Some remarks on domatic numbers of graphs
- Sur le nombre domatique du n-cube et une conjecture de Zelinka. (On the domatic number of the n-cube and a conjecture of Zelinka)
- The Domatic Number Problem in Interval Graphs
- Towards a theory of domination in graphs
Cited in
(43)- On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset
- On the \(b\)-domatic number of graphs
- Constrained domatic bipartition on trees
- Dominating Cartesian products of cycles
- Transitivity on subclasses of bipartite graphs
- When an optimal dominating set with given constraints exists
- Domatic partitions of computable graphs
- Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
- Domination stability in graphs
- Minimal dominating sets in maximum domatic partitions
- On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of the finite poset
- Matched-Factor d-Domatic Coloring of Graphs
- scientific article; zbMATH DE number 3977044 (Why is no real title available?)
- scientific article; zbMATH DE number 3983200 (Why is no real title available?)
- scientific article; zbMATH DE number 125504 (Why is no real title available?)
- scientific article; zbMATH DE number 1735803 (Why is no real title available?)
- scientific article; zbMATH DE number 1161319 (Why is no real title available?)
- A Study on r-Configurations---A Resource Assignment Problem on Graphs
- scientific article; zbMATH DE number 1792633 (Why is no real title available?)
- scientific article; zbMATH DE number 6863896 (Why is no real title available?)
- Domination numbers of planar graphs
- scientific article; zbMATH DE number 1439474 (Why is no real title available?)
- Some new results on the b-domatic number of graphs
- Algorithmic aspects of \(\mathcal{F}\)-domination in graphs
- The upper domatic number of a graph
- Domatically perfect graphs
- Mathematical Foundations of Computer Science 2005
- The Domatic Number Problem in Interval Graphs
- Domatically full Cartesian product graphs
- Domination in Kn\"odel Graphs
- Transitivity on subclasses of chordal graphs
- On domatic number of graphs
- Algorithmic study of \(d_2\)-transitivity of graphs
- Algorithmic study on 2-transitivity of graphs
- Independent coalition in graphs: existence and characterization
- Inverse domination: stability, unique minimum dominating sets, and dual domination
- On complementarily transitivity of graphs
- Tournament transitivity of graphs
- Transitivity in some graph-classes
- Strong transitivity of a graph
- Conceptual clique sampling frameworks to design solution algorithms for the edge clique cover problem
- The \(\{k\}\)-domatic number of a graph
- Dominating sets for split and bipartite graphs
This page was built for publication: The domatic number problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1322260)
