Independent domination in directed graphs

DOI10.22049/CCO.2020.26845.1149MaRDI QIDQ4957541zbMATH OpenOpenAlexFDO

Authors Michael Cary, Jonathan Cary, Savari Prabhu

Publication date 9 September 2021

Full work available at URL https://arxiv.org/abs/1909.05121

zbMATH Keywords

dominating setidomatic numberindependent dominating setindependent dominationindependent set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: In this paper we initialize the study of independent domination in directed graphs. We show that an independent dominating set of an orientation of a graph is also an independent dominating set of the underlying graph, but that the converse is not true in general. We then prove existence and uniqueness theorems for several classes of digraphs including orientations of complete graphs, paths, trees, DAGs, cycles, and bipartite graphs. We also provide the idomatic number for special cases of some of these families of digraphs.

Recommendations

• Independent domination in regular graphs
• Independent domination in finitely defined classes of graphs
• scientific article; zbMATH DE number 734465
• Independent injective domination of graphs
• Independent \((1, 2)\)-domination in graphs
• Domination versus independent domination in regular graphs
• Independent domination in triangle-free graphs
• Independent transversal domination in graphs
• Independent domination subdivision in graphs
• On independent domination of regular graphs

Cites work

• A note on connected bipartite graphs having independent domination number half their order.
• An upper bound for the independent domination number
• Broadcasts in graphs
• Decycling numbers of random regular graphs
• Disjoint independent dominating sets in graphs
• Domination, independent domination, and duality in strongly chordal graphs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 3799700 (Why is no real title available?)
• Idomatic partitions of direct products of complete graphs
• Independent domination in graphs: A survey and recent results
• Independent rainbow domination of graphs
• Minimum independent dominating sets of random cubic graphs
• On a Nordhaus-Gaddum type problem for independent domination
• On approximating the minimum independent dominating set
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• On the independent domination number of graphs with given minimum degree
• On the Independent Domination Number of Random Regular Graphs

Cited in

(10)

• On directed graphs with an independent covering set
• Independent domination in outerplanar graphs
• Independent domination versus weighted independent domination
• scientific article; zbMATH DE number 6949694 (Why is no real title available?)
• The independent compatible edges topology of directed graphs
• Mod-2 independence and domination in graphs
• Domination in some classes of ditrees
• Efficient algorithms for independent Roman domination on some classes of graphs
• Classes of intersection digraphs with good algorithmic properties
• A greedy partition lemma for directed domination

This page was built for publication: Independent domination in directed graphs

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