On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets (Q6063279)

Let \(G\) be a graph and \(k\) a positive integer. By the \(k\)-dominating graph of \(G\), denoted by \(D_k(G)\), we mean the graph whose vertices correspond to the dominating sets of \(G\) that have cardinality less than or equal \(k\). Also, two vertices in the graph \(D_k(G)\) are adjacent if and only if their corresponding dominating sets in \(G\) differ by exactly one element. The dominating graph of \(G\) is denoted by \(D_{|G|}(G)\) of \(G\). By a median graph we mean an undirected graph with the property that every three vertices \(a, b\) and \(c\) of it have a unique median, where by a median of \(a\), \(b\) and \(c\), we mean a vertex that belongs to the shortest paths between each pair of \(a\), \(b\) and \(c\). A partial cube is a graph \(G\) that can be isometrically embedded in a hypercube, meaning that \(G\) can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in \(G\) is the same as the distance between those two vertices in the hypercube. A graph \(G\) is a DM graph if the dominating graph \(D_{|G|}(G)\) of \(G\) is a median graph and is a MDScoMDS graph if the complement of every minimal dominating set of \(G\) is a minimal dominating set. The main results of the paper are as follows: Theorem 1. Let \(G\) be a graph with no isolated vertex and \(G \not \backsimeq C_4\). Then, the following are equivalent. 1. \(G\) is a DM graph. 2. \(G\) is a MDScoMDS graph. 3. Every vertex of \(G\) is either a leaf or adjacent to a leaf. Theorem 2. The dominating graph \(D_{|G|}(G)\) of any graph \(G\) is a partial cube.