Vertex-edge domination in interval and bipartite permutation graphs
Subhabrata Paul, Dinabandhu Pradhan, Shaily Verma · Discussiones Mathematicae Graph Theory · 2021
Given a graph G = (V, E), a vertex u ∈ V ve-dominates all edges incident to any vertex of N G [u].A set D ⊆ V is a vertex-edge dominating set if, for any edge e ∈ E, there exists a vertex u ∈ D such that u ve-dominates e.Given a graph G, our goal is to find a minimum cardinality ve-dominating set of G.In this paper, we designed two linear-time algorithms to find a minimum cardinality ve-dominating set for interval and bipartite permutation graphs.