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 setindependent setindependent dominationindependent dominating setidomatic number

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

• 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?)
• 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
• 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 Random Regular Graphs
• On the independent domination number of graphs with given minimum degree

Cited in

(10)

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