Generalization of the total outer-connected domination in graphs

Rad, Nader Jafari; Volkmann, Lutz

doi:10.1051/ro/2015016

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 [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 \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 \geq 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 $γ_{t c}^{k} (G)$ , is the minimum cardinality of a total outer- $k$ -connected component dominating set of $G$ . We obtain several general results and bounds for $γ_{t c}^{k} (G)$ , and we determine exact values of $γ_{t c}^{k} (G)$ for some special classes of graphs $G$ .

MR Zbl

DOI : 10.1051/ro/2015016

Classification : 05C69
Mots-clés : Total domination, total outer-connected domination

Affiliations des auteurs :

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.

@article{RO_2016__50_2_233_0,
     author = {Rad, Nader Jafari and Volkmann, Lutz},
     title = {Generalization of the total outer-connected domination in graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {233--239},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {2},
     year = {2016},
     doi = {10.1051/ro/2015016},
     mrnumber = {3479866},
     zbl = {1335.05134},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2015016/}
}

TY  - JOUR
AU  - Rad, Nader Jafari
AU  - Volkmann, Lutz
TI  - Generalization of the total outer-connected domination in graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 233
EP  - 239
VL  - 50
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2015016/
DO  - 10.1051/ro/2015016
LA  - en
ID  - RO_2016__50_2_233_0
ER  -

%0 Journal Article
%A Rad, Nader Jafari
%A Volkmann, Lutz
%T Generalization of the total outer-connected domination in graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 233-239
%V 50
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2015016/
%R 10.1051/ro/2015016
%G en
%F RO_2016__50_2_233_0

Rad, Nader Jafari; Volkmann, Lutz. Generalization of the total outer-connected domination in graphs. 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. doi : 10.1051/ro/2015016. http://www.numdam.org/articles/10.1051/ro/2015016/

Bibliographie
Cité par

J. Cyman, Total outer-connected domination in trees. Discuss. Math. Graph Theory 30 (2010) 377–383. | DOI | MR | Zbl

J. Cyman and J. Raczek, Total outer-connected domination numbers in trees. Discrete Appl. Math. 157 (2009) 3198–3202. | DOI | MR | Zbl

J.H. Hattingh and E. Joubert, A note on the total outer-connected domination number of a tree. Akce J. Graphs Combin. 7 (2010) 223–227. | MR | Zbl

T.W. Haynes and S.T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). | MR | Zbl

H.X. Jiang and L.Y. Kang, Inequality of Nordhaus−Gaddum type for total outer-connected domination in graphs. Acta Math. Sinica, English Series 27 (2011) 607–616. | DOI | MR | Zbl

Cité par Sources :