2025/12/13 by Yasemin Büyükçolak, Büyükçolak, Yasemin
Computer Science · #Advanced Graph Theory Research #Interconnection Networks and Systems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2512.12231
Given a graph G=(V, E), a vertex is said to ve-dominate an edge if it is either incident with the edge or adjacent to one of its endpoints. A set of vertices is a ve-dominating set if it ve-dominates every edge of the graph. We introduce the class of well-ve-dominated graphs, defined as graphs in which all minimal ve-dominating sets have the same cardinality. After establishing several general structural properties of well-ve-dominated graphs, we show that recognizing whether a graph belongs to this class is co--NP--complete, highlighting the computational difficulty of the problem. Our main result is a complete structural characterization of well-ve-dominated trees, which yields a simple linear-time recognition algorithm and a constructive description of all trees in this class.