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 –...
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...
Product of digraphs, (super) edge-magic valences and related problems
Product of digraphs, (super) edge-magic valences and related problems
Discrete Mathematics, and in particular Graph Theory, has gained a lot of popularity during the last 7 decades. Among the many branches in Graph Theory, graph labelings has experim...
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...
Certified domination critical graphs upon vertex removal
Certified domination critical graphs upon vertex removal
<p>A set <span class="math inline">\(D\)</span> of vertices of a graph <span class="math inline">\(G=(V_G,E_G)\)</span> is a <span><em>dom...
The Vertex-Edge Locating Roman Domination of Some Graphs
The Vertex-Edge Locating Roman Domination of Some Graphs
In this paper, we introduce the concept of vertex-edge locating Roman dominating functions in graphs. A vertex-edge locating Roman dominating (\({ve} - {LRD}\)) function of a graph...
The Vertex-Edge Locating Roman Domination of Some Graphs
The Vertex-Edge Locating Roman Domination of Some Graphs
In this paper, we introduce the concept of vertex-edge locating Roman dominating functions in graphs. A vertex-edge locating Roman dominating (\(ve-LRD\)) function of a graph \(G=(...