Domination in digraphs and their products
A dominating (respectively, total dominating) set S of a digraph D is a set of vertices in D such that the union of the closed (respectively, open) out-neighborhoods of vertices in S equals the vertex set of D. The minimum size of a dominating (respectively, total dominating) set of D is the domination (respectively, total domination) number of D, denoted γ(D) (respectively,γt(D)). The maximum number of pairwise disjoint closed (respectively,open) in-neighborhoods of D is denoted by ρ(D) (respectively,ρo(D)). We prove that in digraphs whose underlying graphs have girth at least 7, the closed (respectively,open) in-neighborhoods enjoy the Helly property, and use these two results to prove that in any ditree T (that is, a digraph whose underlying graph is a tree), γt(T)=ρo(T) and γ(T)=ρ(T). By using the former equality we then prove that γt(G×T)=γt(G)γt(T), where G is any digraph and T is any ditree, each without a source vertex, and G×T is their direct product. From the equality γ(T)=ρ(T) we derive the bound γ(G□T)≥γ(G)γ(T), where G is an arbitrary digraph, T an arbitrary ditree and G□T is their Cartesian product. In general digraphs this Vizing-type bound fails, yet we prove that for any digraphs G and H, where γ(G)≥γ(H), we have γ(G□H)≥21γ(G)(γ(H)+1). This inequality is sharp as demonstrated by an infinite family of examples. Ditrees T and digraphs H enjoying γ(T□H)=γ(T)γ(H) are also investigated.
