Independent domination in directed graphs
From MaRDI portal
Publication:4957541
DOI10.22049/CCO.2020.26845.1149zbMATH Open1488.05368arXiv1909.05121OpenAlexW3085817308MaRDI QIDQ4957541FDOQ4957541
Authors: Michael Cary, Jonathan Cary, Savari Prabhu 
Publication date: 9 September 2021
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.
Full work available at URL: https://arxiv.org/abs/1909.05121
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
Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On approximating the minimum independent dominating set
- Independent domination in graphs: A survey and recent results
- Domination, independent domination, and duality in strongly chordal graphs
- Decycling numbers of random regular graphs
- Broadcasts in graphs
- An upper bound for the independent domination number
- On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
- Disjoint independent dominating sets in graphs
- Minimum independent dominating sets of random cubic graphs
- On the Independent Domination Number of Random Regular Graphs
- Idomatic partitions of direct products of complete graphs
- Title not available (Why is that?)
- Independent rainbow domination of graphs
- On the independent domination number of graphs with given minimum degree
- On a Nordhaus-Gaddum type problem for independent domination
- A note on connected bipartite graphs having independent domination number half their order.
Cited In (10)
- Independent domination in outerplanar graphs
- Domination in some classes of ditrees
- A greedy partition lemma for directed domination
- On directed graphs with an independent covering set
- Independent domination versus weighted independent domination
- Mod-2 independence and domination in graphs
- Classes of intersection digraphs with good algorithmic properties
- Title not available (Why is that?)
- Efficient algorithms for independent Roman domination on some classes of graphs
- The independent compatible edges topology of directed graphs
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)
