Worst-case efficient dominating sets in digraphs

2012/01/09 by Italo J. Dejter, Dejter, Italo J.
Computer Science · Engineering · Mathematics · #05C69 #68R10 #94B25 #94C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Interconnection Networks and Systems #cs.IT #graph theory and CDMA systems #math.CO #math.IT #msc:05C69 #msc:68R10 #msc:94B25 #msc:94C15

paper · pdf · doi:10.48550/arxiv.1201.1728

13 pages, 3 figures

openalex publication_date 2012/01/09 · arxiv created 2012/06/26 · arxiv updated 2012/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let 1≤ n∈\Z. \it Worst-case efficient dominating sets in digraphs are conceived so that their presence in certain strong digraphs ST_n corresponds to that of efficient dominating sets in star graphs ST_n: The fact that the star graphs ST_n form a so-called dense segmental neighborly E-chain is reflected in a corresponding fact for the digraphs ST_n. Related chains of graphs and open problems are presented as well.

Related

• Efficient closed domination in digraph products
• Graphs that are simultaneously efficient open domination and efficient closed domination graphs
• Secure Domination in Digraphs
• Efficient domination in regular graphs
• Disjoint dominating and 2-dominating sets in graphs