Back to Search
Start Over
Total outer connected vertex-edge domination.
- Source :
- Discrete Mathematics, Algorithms & Applications; Jan2023, Vol. 15 Issue 1, p1-12, 12p
- Publication Year :
- 2023
-
Abstract
- A vertex v of a graph is said to v e r t e x - e d g e dominate every edge incident with v , as well as every edge incident to vertices adjacent to v. A subset D ⊆ V is a total outer connected vertex-edge dominating set of a graph G if every edge in G is v e r t e x - e d g e dominated by a vertex in D , the subgraph induced by D has no isolated vertices and the subgraph induced by V (G) ∖ D is connected. We initiate the study of total outer connected vertex-edge domination in graphs. We show that the decision problem for total outer-connected vertex-edge domination problem is N P -Complete even for bipartite graphs. We prove that for every tree of order n ≥ 3 with l leaves, γ tve oc (T) ≥ 2 (n − l + 1) / 3 and characterize the trees attaining the lower bound. We also study the effect of edge removal, edge addition and edge subdivision on total outer connected vertex-edge domination number of a graph. [ABSTRACT FROM AUTHOR]
- Subjects :
- DOMINATING set
BIPARTITE graphs
STATISTICAL decision making
Subjects
Details
- Language :
- English
- ISSN :
- 17938309
- Volume :
- 15
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Discrete Mathematics, Algorithms & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 161657293
- Full Text :
- https://doi.org/10.1142/S1793830922500574