General sharp upper bounds on the total coalition number
Preprint
Abstract
Let $G(V,E)$ be a finite, simple, isolate-free graph. Two disjoint sets $A,B\subset V$ form a total coalition in $G$, if none of them is a total dominating set, but their union $A\cup B$ is a total dominating set. A vertex partition $\Psi=\{C_1,C_2,\dots,C_k\}$ is a total coalition partition, if none of the partition classes is a total dominating set, meanwhile for every $i\in\{1,2,\dots,k\}$ there exists a distinct $j\in\{1,2,\dots,k\}$ such that $C_i$ and $C_j$ form a total coalition. The maximum cardinality of a total coalition partition of $G$ is the total coalition number of $G$ and denoted by $TC(G)$. We give a general sharp upper bound on the total coalition number as a function of the maximum degree. We further investigate this optimal case and study the total coalition graph. Analogous to previous work on coalition graphs, we show that every graph can be realised as a total coalition graph.
Keywords
All Related Versions
This publication has 2 references indexed in Scilit:
- Introduction to coalitions in graphsAKCE International Journal of Graphs and Combinatorics, 2020
- Independent domination in graphs: A survey and recent resultsDiscrete Mathematics, 2013