Generalization of the total outer-connected domination in graphs

¹ Department of Mathematics, Shahrood University of Technology, P.O. Box 3619995161, Shahrood, Iran.
n.jafarirad@shahroodut.ac.ir
² Lehrstuhl II für Mathematik, RWTH Aachen University, Templergraben 55, 52056 Aachen, Germany.
volkm@math2.rwth-aachen.de

Received: 18 May 2015
Accepted: 1 June 2015

Abstract

Let G = (V,E) be a graph without an isolated vertex. A set S ⊆ V is a total dominating set if S is a dominating set, and the induced subgraph G [ S ] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total dominating set of G. A set D ⊆ V is a total outer-connected dominating set if D is a total dominating set, and the induced subgraph G [ V − D ] is connected. The total outer-connected domination number of G is the minimum cardinality of a total outer-connected dominating set of G. In this paper we generalize the total outer-connected domination number in graphs. Let k ≥ 1 be an integer. A set D ⊆ V is a total outer-k-connected component dominating set if D is a total dominating and the induced subgraph G [ V − D ] has exactly k connected component(s). The total outer-k-connected component domination number of G, denoted by γ^k_tc(G) , is the minimum cardinality of a total outer-k-connected component dominating set of G. We obtain several general results and bounds for γ^k_tc(G), and we determine exact values of γ^k_tc(G) for some special classes of graphs G.