A note on total co-independent domination in trees

• Published in: arXiv.org 2020-05
• Main Authors: Abel Cabrera Martínez, Hernández Mira, Frank A, José M Sigarreta Almira, Yero, Ismael G
• Format: Article
• Language: English
• Subjects: Apexes; Graph theory; Leaves; Trees (mathematics)
• ISSN: 2331-8422

A set \(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 domination number of \(G\) is the minimum cardinality of any total dominating set of \(G\) and is denoted by \(\gamma_t(G)\). The total dominating set \(D\) is called a total co-independent dominating set if \(V(G)\setminus D\) is an independent set and has at least one vertex. The minimum cardinality of any total co-independent dominating set is denoted by \(\gamma_{t,coi}(G)\). In this paper, we show that, for any tree \(T\) of order \(n\) and diameter at least three, \(n-\beta(T)\leq \gamma_{t,coi}(T)\leq n-|L(T)|\) where \(\beta(T)\) is the maximum cardinality of any independent set and \(L(T)\) is the set of leaves of \(T\). We also characterize the families of trees attaining the extremal bounds above and show that the differences between the value of \(\gamma_{t,coi}(T)\) and these bounds can be arbitrarily large for some classes of trees.