On well-edge-dominated graphs

DOI10.1007/S00373-022-02508-9zbMATH Open1496.05121arXiv2110.07133OpenAlexW3205020919MaRDI QIDQ2673496FDOQ2673496

Authors: Sarah E. Anderson, Kirsti Kuenzel, Douglas F. Rall 

Publication date: 10 June 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: 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 $GBoxH$ is well-edge-dominated, where $G$ and $H$ have order at least $2$, if and only if $GBoxH=K_{2}Box{K}_2$.

Full work available at URL: https://arxiv.org/abs/2110.07133

Recommendations

• On well-dominated graphs
• On well-dominated direct, Cartesian and strong product graphs
• scientific article; zbMATH DE number 4063149
• On the well-coveredness of Cartesian products of graphs
• scientific article; zbMATH DE number 2068372

zbMATH Keywords

split graphCartesian productequimatchablewell-edge-dominated

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Edge Dominating Sets in Graphs
• Minimum Edge Dominating Sets
• Title not available (Why is that?)
• Randomly matchable graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Linear time algorithms for generalized edge dominating set problems
• Matching-perfect and cover-perfect graphs
• Title not available (Why is that?)
• The edge domination problem
• Triangle‐free equimatchable graphs

Cited In (5)

• Well paired-dominated graphs
• On well-dominated graphs
• A characterization of well-dominated Cartesian products
• On well-dominated direct, Cartesian and strong product graphs
• Correction to: ``On well-edge-dominated graphs

This page was built for publication: On well-edge-dominated graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2673496)