Efficient Domination in Directed Tori and the Vizing’s Conjecture for Directed Graphs

Abstract

Though the well-known Vizing’s conjecture is not true for directed graphs in general, we show that it is true when the digraph and its reversal contain an efficient dominating set. In this paper, we investigate the existence of such sets in directed tori and infinite grids. We give a complete characterization of efficient dominating sets in the $3$-dimensional case and show the nonexistence of efficient $d$-dominating sets in directed tori for any $d>1$ and any dimension $n>1$.