On the Total Outer <i>k</i>-Independent Domination Number of Graphs
A set of vertices of a graph <i>G</i> is a total dominating set if every vertex of <i>G</i> is adjacent to at least one vertex in such a set. We say that a total dominating set <i>D</i> is a total outer <i>k</i>-independent dominating set of <i>G...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-02-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/2/194 |
| _version_ | 1818160056969986048 |
|---|---|
| author | Abel Cabrera-Martínez Juan Carlos Hernández-Gómez Ernesto Parra-Inza José María Sigarreta Almira |
| author_facet | Abel Cabrera-Martínez Juan Carlos Hernández-Gómez Ernesto Parra-Inza José María Sigarreta Almira |
| author_sort | Abel Cabrera-Martínez |
| collection | DOAJ |
| description | A set of vertices of a graph <i>G</i> is a total dominating set if every vertex of <i>G</i> is adjacent to at least one vertex in such a set. We say that a total dominating set <i>D</i> is a total outer <i>k</i>-independent dominating set of <i>G</i> if the maximum degree of the subgraph induced by the vertices that are not in <i>D</i> is less or equal to <inline-formula> <math display="inline"> <semantics> <mrow> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula>. The minimum cardinality among all total outer <i>k</i>-independent dominating sets is the total outer <i>k</i>-independent domination number of <i>G</i>. 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 <i>k</i>-independent domination number of a graph <i>G</i> is an NP-hard problem. |
| first_indexed | 2024-12-11T15:55:49Z |
| format | Article |
| id | doaj.art-c040516f69a34f8aaaa39cd988bee4dd |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-12-11T15:55:49Z |
| publishDate | 2020-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-c040516f69a34f8aaaa39cd988bee4dd2022-12-22T00:59:26ZengMDPI AGMathematics2227-73902020-02-018219410.3390/math8020194math8020194On the Total Outer <i>k</i>-Independent Domination Number of GraphsAbel Cabrera-Martínez0Juan Carlos Hernández-Gómez1Ernesto Parra-Inza2José María Sigarreta Almira3Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, SpainFacultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame 5, Col. La Garita 39650, Acapulco, MexicoFacultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame 5, Col. La Garita 39650, Acapulco, MexicoFacultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame 5, Col. La Garita 39650, Acapulco, MexicoA set of vertices of a graph <i>G</i> is a total dominating set if every vertex of <i>G</i> is adjacent to at least one vertex in such a set. We say that a total dominating set <i>D</i> is a total outer <i>k</i>-independent dominating set of <i>G</i> if the maximum degree of the subgraph induced by the vertices that are not in <i>D</i> is less or equal to <inline-formula> <math display="inline"> <semantics> <mrow> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula>. The minimum cardinality among all total outer <i>k</i>-independent dominating sets is the total outer <i>k</i>-independent domination number of <i>G</i>. 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 <i>k</i>-independent domination number of a graph <i>G</i> is an NP-hard problem.https://www.mdpi.com/2227-7390/8/2/194total outer k-independent dominationtotal dominationk-independence |
| spellingShingle | Abel Cabrera-Martínez Juan Carlos Hernández-Gómez Ernesto Parra-Inza José María Sigarreta Almira On the Total Outer <i>k</i>-Independent Domination Number of Graphs Mathematics total outer k-independent domination total domination k-independence |
| title | On the Total Outer <i>k</i>-Independent Domination Number of Graphs |
| title_full | On the Total Outer <i>k</i>-Independent Domination Number of Graphs |
| title_fullStr | On the Total Outer <i>k</i>-Independent Domination Number of Graphs |
| title_full_unstemmed | On the Total Outer <i>k</i>-Independent Domination Number of Graphs |
| title_short | On the Total Outer <i>k</i>-Independent Domination Number of Graphs |
| title_sort | on the total outer i k i independent domination number of graphs |
| topic | total outer k-independent domination total domination k-independence |
| url | https://www.mdpi.com/2227-7390/8/2/194 |
| work_keys_str_mv | AT abelcabreramartinez onthetotalouterikiindependentdominationnumberofgraphs AT juancarloshernandezgomez onthetotalouterikiindependentdominationnumberofgraphs AT ernestoparrainza onthetotalouterikiindependentdominationnumberofgraphs AT josemariasigarretaalmira onthetotalouterikiindependentdominationnumberofgraphs |