Graphs with unique minimum vertex-edge dominating sets

¹ Department of Mathematics, SASTRA Deemed University, Tanjore, Tamilnadu, India
² LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270 Blida, Algeria

^* Corresponding author: venkatakrish2@maths.sastra.edu

Received: 13 May 2022
Accepted: 30 May 2023

Abstract

A vertex u of a graph G = (V, E), ve-dominates every edge incident to u, as well as every edge adjacent to these incident edges. A set S ⊆ V is a vertex-edge dominating set (or a ved-set for short) if every edge of E is ve-dominated by at least one vertex of S. The vertex-edge domination number is the minimum cardinality of a ved-set in G. In this paper, we investigate the graphs having unique minimum ved-sets that we will call UVED-graphs. We start by giving some basic properties of UVED-graphs. For the class of trees, we establish two equivalent conditions characterizing UVED-trees which we subsequently complete by providing a constructive characterization.