Generalization of the total outer-connected domination in graphs

Rad, Nader Jafari¹ ; Volkmann, Lutz²

¹ Department of Mathematics, Shahrood University of Technology, P.O. Box 3619995161, Shahrood, Iran.
² Lehrstuhl II für Mathematik, RWTH Aachen University, Templergraben 55, 52056 Aachen, Germany.

RAIRO - Operations Research - Recherche Opérationnelle, Special issue: Research on Optimization and Graph Theory dedicated to COSI 2013 / Special issue: Recent Advances in Operations Research in Computational Biology, Bioinformatics and Medicine, Tome 50 (2016) no. 2, pp. 233-239

Résumé

Let $G=(V,E)$ be a graph without an isolated vertex. A set $S\subseteq V$ is a total dominating set if $S$ is a dominating set, and the induced subgraph $G\left[S\right]$ 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\subseteq 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\ge 1$ be an integer. A set $D\subseteq 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 ${\gamma }_{tc}^k\left(G\right)$, is the minimum cardinality of a total outer-$k$-connected component dominating set of $G$. We obtain several general results and bounds for ${\gamma }_{tc}^k\left(G\right)$, and we determine exact values of ${\gamma }_{tc}^k\left(G\right)$ for some special classes of graphs $G$.

Détail

DOI : 10.1051/ro/2015016

Classification : 05C69
Keywords: Total domination, total outer-connected domination