The algorithmic complexity of domination digraphs

MaRDI QIDQ2895354zbMATH OpenFDO

Authors Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, Alice A. McRae

Publication date 2 July 2012

Published in JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing (Search for Journal in Brave)

zbMATH Keywords

complexitydigraphdomatic numberdomatic partitiondomination digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Partitioning vertices into in- and out-dominating sets in digraphs
• Domatic partitions of computable graphs
• Domination in digraphs
• The algorithmic complexity of \(k\)-domatic partition of graphs
• Gallai colorings and domination in multipartite digraphs

Cited in

(7)

• More results on the complexity of domination problems in graphs
• The algorithmic complexity of minus domination in graphs
• A decidability result for the dominating set problem
• The upper domatic number of a graph
• Mod-2 independence and domination in graphs
• Fundamentals of Computation Theory
• Domination graphs: Examples and counterexamples

This page was built for publication: The algorithmic complexity of domination digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2895354)