Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Algorithmic Aspects of Vertex-edge Domination in Some Graphs
View through CrossRef
Let \(G=(V,E)\) be a simple graph. A vertex \(v\in V(G)\) ve-dominates every edge \(uv\) incident to \(v\), as well as every edge adjacent to these incident edges. A set \(D\subseteq V(G)\) is a vertex-edge dominating set if every edge of \(E(G)\) is ve-dominated by a vertex of \(D.\) The MINIMUM VERTEX-EDGE DOMINATION problem is to find a vertex-edge dominating set of minimum cardinality. A linear time algorithm to find the minimum vertex-edge dominating set for proper interval graphs is proposed. The vertex-edge domination problem is proved to be APX-complete for bounded-free graphs and NP-Complete for Chordal bipartite and Undirected Path graphs.
Title: Algorithmic Aspects of Vertex-edge Domination in Some Graphs
Description:
Let \(G=(V,E)\) be a simple graph.
A vertex \(v\in V(G)\) ve-dominates every edge \(uv\) incident to \(v\), as well as every edge adjacent to these incident edges.
A set \(D\subseteq V(G)\) is a vertex-edge dominating set if every edge of \(E(G)\) is ve-dominated by a vertex of \(D.
\) The MINIMUM VERTEX-EDGE DOMINATION problem is to find a vertex-edge dominating set of minimum cardinality.
A linear time algorithm to find the minimum vertex-edge dominating set for proper interval graphs is proposed.
The vertex-edge domination problem is proved to be APX-complete for bounded-free graphs and NP-Complete for Chordal bipartite and Undirected Path graphs.
Related Results
Domination of Polynomial with Application
Domination of Polynomial with Application
In this paper, .We .initiate the study of domination. polynomial , consider G=(V,E) be a simple, finite, and directed graph without. isolated. vertex .We present a study of the Ira...
THE FORCING EDGE FIXING EDGE-TO-VERTEX MONOPHONIC NUMBER OF A GRAPH
THE FORCING EDGE FIXING EDGE-TO-VERTEX MONOPHONIC NUMBER OF A GRAPH
For a connected graph G = (V, E), a set Se ⊆ E(G)–{e} is called an edge fixing edge-to-vertex monophonic set of an edge e of a connected graph G if every vertex of G lies on an e –...
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Abstract
Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characteriz...
Independent Set in Neutrosophic Graphs
Independent Set in Neutrosophic Graphs
New setting is introduced to study neutrosophic independent number and independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key term to have th...
Failed Independent Number in Neutrosophic Graphs
Failed Independent Number in Neutrosophic Graphs
New setting is introduced to study neutrosophic failed-independent number and failed independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key t...
Completion and decomposition of hypergraphs by domination hypergraphs
Completion and decomposition of hypergraphs by domination hypergraphs
A graph consists of a finite non-empty set of vertices and a set of unordered pairs of vertices, called edges. A dominating set of a graph is a set of vertices D such that every ve...
Magic graphs
Magic graphs
DE LA TESIS<br/>Si un graf G admet un etiquetament super edge magic, aleshores G es diu que és un graf super edge màgic. La tesis està principalment enfocada a l'estudi del c...
Total edge–vertex domination
Total edge–vertex domination
An edge e ev-dominates a vertex v which is a vertex of e, as well as every vertex adjacent to v. A subset D ⊆ E is an edge-vertex dominating set (in simply, ev-dominating set) of G...