On well-edge-dominated graphs (Q2673496)

A graph is said to be well-edge-dominated if all its minimal edge-dominating sets are minimum. A graph is said to be an equimatchable graph if all of its maximal matchings have the same cardinality, in other words every maximal matching is maximum matching. The graph \(C_7^\ast\) is the graph obtained from \(C_7\) by adding a chord between two vertices of \(C_7\) that are distance \(3\) apart. For graphs \(G\) and \(H\), the Cartesian product of \(G\) and \(H\) is denoted by \(G\square H\). The girth of an undirected graph is the length of the shortest cycle contained in the graph. Two main results of the paper are as follows. Theorem 1. If \(G\) is a connected, non-bipartite, well-edge-dominated graph of girth at least \(4\), then \(G\in \{C_5, C_7, C_7^\ast\}\). Theorem 2. Let \(G\) and \(H\) be two connected, nontrivial graphs. The following statements are equivalent. (a) \(G\square H\) is equimatchable. (b) \(G\square H\) is well-edge-dominated. (c) \(G=H=K_2\). Furthermore, some open problems are shown in the paper.