2019/09/11 by Michael Cary, Cary, Michael, Jonathan Cary +3
Computer Science · #05C20 #05C69 #94A05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1909.05121
openalex publication_date 2019/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.