Search

We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing’s conjecture. The new framework unifies two different approaches to the conjecture. The most common approach restricts one of the factors of the product to some class of graphs and proves the inequality of the conjecture then holds when the other factor is any graph. The other approach utilizes the so-called Clark-Suen partition for proving a weaker inequality that holds for all pairs of graphs. We demonstrate the strength of our framework by improving the bound of Clark and Suen as follows: γ (X□Y) ≥ max γ(X□Y)≥max{12γ(X)γt(Y),12γt(X)γ(Y)}\gamma \left( {X \square Y} \right) \ge \max \left\{ {{1 \over 2}\gamma (X){\gamma _t}(Y),{1 \over 2}{\gamma _t}(X)\gamma (Y)} \right\}, where γ stands for the domination number, γt is the total domination number, and X□Y is the Cartesian product of graphs X and Y.

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 (i.e., 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)≥12γ(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. [ABSTRACT FROM AUTHOR]

A graph is well-dominated if all its minimal dominating sets have the same cardinality. In this paper we prove that at least one factor of every connected, well-dominated Cartesian product is a complete graph, which then allows us to give a complete characterization of the connected, well-dominated Cartesian products if both factors have order at least 2. In particular, we show that G □ H is well-dominated if and only if G □ H = P 3 □ K 3 or G □ H = K n □ K n for some n ≥ 2. [ABSTRACT FROM AUTHOR]

If each minimal dominating set in a graph is a minimum dominating set, then the graph is called well-dominated. Since the seminal paper on well-dominated graphs appeared in 1988, the structure of well-dominated graphs from several restricted classes has been studied. In this paper we give a complete characterization of nontrivial direct products that are well-dominated. We prove that if a strong product is well-dominated, then both of its factors are well-dominated. When one of the factors of a strong product is a complete graph, the other factor being well-dominated is also a sufficient condition for the product to be well-dominated. Our main result gives a complete characterization of well-dominated Cartesian products in which at least one of the factors is a complete graph. In addition, we conjecture that this result is actually a complete characterization of the class of nontrivial, well-dominated Cartesian products. [ABSTRACT FROM AUTHOR]