Article in press
Authors:
Zoltán L. Blázsik
Rényi Institute, ELKH-ELTE Geometric and Algebraic Combinatorics Research Group, University of Szeged
email: blazsik@renyi.hu
Title:
General sharp upper bounds on the total coalition number
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-03-08 , Revised: 2023-07-20 , Accepted: 2023-07-20 , Available online: 2023-08-23 , https://doi.org/10.7151/dmgt.2511
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. We show that every graph can be realised as
a total coalition graph.
Keywords:
total domination, total coalition partition, total coalition number, total coalition graph
References:
- S. Alikhani, D. Bakhshesh and H. Golmohammadi, Total coalitions in graphs (2022).
arXiv: 2211.11590 - E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219.
https://doi.org/10.1002/net.3230100304 - E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247–261.
https://doi.org/10.1002/net.3230070305 - W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013) 839–854.
https://doi.org/10.1016/j.disc.2012.11.031 - W. Goddard and M.A. Henning, Thoroughly dispersed colorings, J. Graph Theory 88 (2018) 174–191.
https://doi.org/10.1002/jgt.22204 - T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Comb. 17 (2020) 653–659.
https://doi.org/10.1080/09728600.2020.1832874 - T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Upper bounds on the coalition number, Australas. J. Combin. 80 (2021) 442–453.
- T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Coalition graphs, Commun. Comb. Optim. 8 (2023) 423–430.
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Boca Raton, CRC Press, 1998).
https://doi.org/10.1201/9781482246582 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
https://doi.org/10.1201/9781315141428 - M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013).
- M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009) 32–63.
https://doi.org/10.1007/978-1-4614-6525-6
Close