Search

In [16] Nowakowski and Rall listed a series of conjectures involving several different graph products. In particular, they conjectured that i (G × H) ≥ i (G) i (H) where i(G) is the independent domination number of G and G × H is the direct product of graphs G and H. We show this conjecture is false, and, in fact, construct pairs of graphs for which min { i (G) , i (H) } - i (G × H) is arbitrarily large. We also give the exact value of i (G × K n) when G is either a path or a cycle. [ABSTRACT FROM AUTHOR]

A graph is said to be well-edge-dominated if all its minimal edge dominating sets are minimum. It is known that every well-edge-dominated graph G is also equimatchable, meaning that every maximal matching in G is maximum. In this paper, we show that if G is a connected, triangle-free, nonbipartite, well-edge-dominated graph, then G is one of three graphs. We also characterize the well-edge-dominated split graphs and Cartesian products. In particular, we show that a connected Cartesian product G □ H is well-edge-dominated, where G and H have order at least 2, if and only if G □ H = K 2 □ K 2 . We also prove that the Cartesian product of two connected, nontrivial graphs is well-edge-dominated if and only if it is equimatchable. [ABSTRACT FROM AUTHOR]

A graph is well-dominated if all of its minimal dominating sets have the same cardinality. It is proved that there are exactly eleven connected, well-dominated, triangle-free graphs whose domination number is at most 3. We prove that at least one of the factors is well-dominated if the Cartesian product of two graphs is well-dominated. In addition, we show that the Cartesian product of two connected, triangle-free graphs is well-dominated if and only if both graphs are complete graphs of order 2. Under the assumption that at least one of the connected graphs G or H has no isolatable vertices, we prove that the direct product of G and H is well-dominated if and only if either G = H = K 3 or G = K 2 and H is either the 4-cycle or the corona of a connected graph. Furthermore, we show that the disjunctive product of two connected graphs is well-dominated if and only if one of the factors is a complete graph and the other factor has domination number at most 2. [ABSTRACT FROM AUTHOR]