On well-edge-dominated graphs (Q2673496)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On well-edge-dominated graphs |
scientific article |
Statements
On well-edge-dominated graphs (English)
0 references
10 June 2022
0 references
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.
0 references
well-edge-dominated
0 references
split graph
0 references
equimatchable
0 references
Cartesian product
0 references