Some Results on Total Outer-Paired Dominating Sets in Graphs

Subject Areas : Algebra

Akram Mahmoodi ¹ , Alireza Najafizadeh ²

1 - Department of Mathematics, Payame Noor University, PO BOX 19395-3697 Tehran, IRAN
2 - Department of Mathematics. Payame Noor University, PO BOX 19395-3697 Tehran.IRAN,

Received: 2020-06-30 Accepted : 2022-09-08 Published : 2022-03-21

Keywords: تطابق, کمر, احاطه‌گر تام, احاطه‌گر,

Abstract :

Let G=(V, E) be a simple graph with vertex set V and edge set E. An outer-paired dominating set D of a graph G is a dominating set such that the subgraph induced by V\D has a perfect matching. The outer-paired domination number of G denoted by is the minimum cardinality of an outer-paired dominating set of G. Moreover, a total outer-paired dominating set D of a graph G is a total dominating set such that the subgraph induced by V\D has a perfect matching. The total outer-paired domination number of G denoted by is the minimum cardinality of a total outer-paired dominating set of G. In this paper, besides introducing such a notion for a graph, we study some fundamental properties of this invariant. Furthermore, we present some bounds in terms of the order, the size, the girth of a graph and etc. Finally, the well-known Nordhaus-Gaddum inequality is obtained for regular graphs.

References:

 [1] H. A. Ahangar, M. Chellali, D. Kuziak, and V. Samodivkin, Connected graphs with maximal Roman domination numbers one less than their order n, Ars Combinatoria, 144 (2019) 207-224.

 

[2] M. H. Akhbari, R. Hasni, O. Favaron, H. Karami, and S.M. Sheikholeslami, On the outer-connected domination in graphs, Journal of Combinatorial Optimization, 26 (2013) 10-18.

 

[3] R. B. Allan and R.C. Laskar, On domination and independent domination numbers of a graph, Discrete Mathematics, 23 (1978) 73-76.

 

 [4] M. Atapour and N. Soltankhah, On total dominating sets in graphs, Int. J. Contemp. Math. Sciences, 4 (2009) 253-257.

 

 [5] P. Azizi Keshavarz and A. Tehranian, Incidence dominating numbers of graphs, Journal of New Researches in Mathematics, 6(24) (2020) 85-96.

[6] B. Brešar, M. A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese Journal of Mathematics, 12 (2008) 213-225.

 

[7] B. Brešar and T.K. Šumenjak, On the 2- rainbow domination in graphs, Discrete Applied Mathematics 155 (2007) 2394-2400.

 

[8] E. J. Cockayne, R.M. Dawes and S. T. Hedetniemi, Total domination in graphs,  Networks 10 (1980) 211-219.

 

[9] T. W. Haynes and P. J. Slater, Paired domination in graphs, Networks 32 (1998) 199-206.

 

[10] M. kamali Pashakalai, H. A. Ahangar, M. Motiei and S. M. Sheikholeslami,  Results on the maximal Roman domination number in graphs, Journal of New Researches in Mathematics, 6 (25) (2020) 197-208.

[11] Ch. Y. Lin, J. J. Liu, Y. L. Wang and Ch. Ch. Hsu, Dominating sets with matching outside, The 32^nd workshop on Combinatorial Mathematics and Computation Theory.

[12] A. Mahmoodi, L. Asgharsharghi, Outer-paired domination in graphs, Discrete Mathematics, Algorithms and Applications 12(6), 2050072 (2020).

[13] H. Rahbani, S. N. Doosti Motlagh and N. Jafari Rad, New bounds on weak odd dominating set in trees, Journal of New Researches in Mathematics, (2021).