On computational and combinatorial properties of the total co-independent domination number of graphs
| Autor: | Martinez, Abel Cabrera, Mira, Frank A. Hernandez, Almira, Jose M. Sigarreta, Yero, Ismael G. |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A subset $D$ of vertices of a graph $G$ is a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $D$. The total dominating set $D$ is called a total co-independent dominating set if the subgraph induced by $V-D$ is edgeless and has at least one vertex. The minimum cardinality of any total co-independent dominating set is the total co-independent domination number of $G$ and is denoted by $\gamma_{t,coi}(G)$. In this work we study some complexity and combinatorial properties of $\gamma_{t,coi}(G)$. Specifically, we prove that deciding whether $\gamma_{t,coi}(G)\le k$ for a given integer $k$ is an NP-complete problem and give several bounds on $\gamma_{t,coi}(G)$. Also, since any total co-independent dominating set is also a total dominating set, we characterize all the trees having equal total co-independent domination number and total domination number. Comment: 22 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|