Total outer connected vertex-edge domination.

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]