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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references