On well-edge-dominated graphs

2021/10/14 by Sarah Anderson, Anderson, Sarah E., Kirsti Kuenzel +3 · 1 citation
Computer Science · #05C69 #05C75 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2110.07133

openalex publication_date 2021/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₂ \Box K₂.

Cited by

• Characterizing all K₄-free well-edge-dominated graphs of girth 3

Related

• On well (edge) dominated and equimatchable strong product graphs
• On well-dominated graphs
• A characterization of well-dominated Cartesian products
• On well-dominated direct, Cartesian and strong product graphs
• Well-edge-dominated graphs containing triangles