Back to Search
Start Over
On well-edge-dominated graphs
- Publication Year :
- 2021
-
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 $G\Box H$ is well-edge-dominated, where $G$ and $H$ have order at least $2$, if and only if $G\Box H = K_2 \Box K_2$.<br />Comment: 18 pages, 2 figures, 18 references
- Subjects :
- Mathematics - Combinatorics
05C69, 05C76, 05C75
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2110.07133
- Document Type :
- Working Paper