On the Total Outer k -Independent Domination Number of Graphs

Abel Cabrera-Martínez, Juan Carlos Hernández-Gómez, Ernesto Parra-Inza and José María Sigarreta Almira
Additional contact information
Abel Cabrera-Martínez: Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, Spain
Juan Carlos Hernández-Gómez: Facultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame 5, Col. La Garita 39650, Acapulco, Mexico
Ernesto Parra-Inza: Facultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame 5, Col. La Garita 39650, Acapulco, Mexico
José María Sigarreta Almira: Facultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame 5, Col. La Garita 39650, Acapulco, Mexico

Mathematics, 2020, vol. 8, issue 2, 1-14

Abstract: A set of vertices of a graph G is a total dominating set if every vertex of G is adjacent to at least one vertex in such a set. We say that a total dominating set D is a total outer k -independent dominating set of G if the maximum degree of the subgraph induced by the vertices that are not in D is less or equal to k − 1 . The minimum cardinality among all total outer k -independent dominating sets is the total outer k -independent domination number of G . In this article, we introduce this parameter and begin with the study of its combinatorial and computational properties. For instance, we give several closed relationships between this novel parameter and other ones related to domination and independence in graphs. In addition, we give several Nordhaus–Gaddum type results. Finally, we prove that computing the total outer k -independent domination number of a graph G is an NP-hard problem.

Keywords: total outer k-independent domination; total domination; k-independence (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/2/194/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/2/194/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:2:p:194-:d:316588

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().