From the Quasi-Total Strong Differential to Quasi-Total Italian Domination in Graphs
Open Access
Abstract
This paper is devoted to the study of the quasi-total strong differential of a graph, and it is a contribution to the Special Issue “Theoretical computer science and discrete mathematics” of Symmetry. Given a vertex of a graph G, the neighbourhood of x is denoted by . The neighbourhood of a set is defined to be , while the external neighbourhood of X is defined to be . Now, for every set and every vertex , the external private neighbourhood of x with respect to X is defined as the set Let . The strong differential of X is defined to be , while the quasi-total strong differential of G is defined to be We show that the quasi-total strong differential is closely related to several graph parameters, including the domination number, the total domination number, the 2-domination number, the vertex cover number, the semitotal domination number, the strong differential, and the quasi-total Italian domination number. As a consequence of the study, we show that the problem of finding the quasi-total strong differential of a graph is NP-hard.
Keywords
This publication has 16 references indexed in Scilit:
- Quasi-total Roman Domination in GraphsResults in Mathematics, 2019
- On the differential and Roman domination number of a graph with minimum degree twoDiscrete Applied Mathematics, 2017
- Italian domination in treesDiscrete Applied Mathematics, 2017
- Roman -dominationDiscrete Applied Mathematics, 2016
- Relations between the differential and parameters in graphsElectronic Notes in Discrete Mathematics, 2014
- The differential and the roman domination number of a graphApplicable Analysis and Discrete Mathematics, 2014
- Differentials in certain classes of graphsTamkang Journal of Mathematics, 2010
- Roman domination in graphsDiscrete Mathematics, 2004
- A note on the k‐domination number of a graphInternational Journal of Mathematics and Mathematical Sciences, 1989
- On the corona of two graphsAequationes mathematicae, 1970