Geodesic
General sharp upper bounds on the total coalition number
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1567-1584 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Let G(V,E) be a finite, simple, isolate-free graph. Two disjoint sets A,B⊂ V form a total coalition in G, if none of them is a total dominating set, but their union A∪ B is a total dominating set. A vertex partition Ψ={C_1,C_2,...,C_k} is a total coalition partition, if none of the partition classes is a total dominating set, meanwhile for every i∈{1,2,...,k} there exists a distinct j∈{1,2,...,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 
@article{DMGT_2024_44_4_a17,
     author = {Bar\'at, J\'anos and Bl\'azsik, Zolt\'an},
     title = {General sharp upper bounds on the total coalition number},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1567--1584},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a17/}
}
TY  - JOUR
AU  - Barát, János
AU  - Blázsik, Zoltán
TI  - General sharp upper bounds on the total coalition number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1567
EP  - 1584
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a17/
LA  - en
ID  - DMGT_2024_44_4_a17
ER  - 
%0 Journal Article
%A Barát, János
%A Blázsik, Zoltán
%T General sharp upper bounds on the total coalition number
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1567-1584
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a17/
%G en
%F DMGT_2024_44_4_a17
Barát, János; Blázsik, Zoltán. General sharp upper bounds on the total coalition number. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1567-1584. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a17/

[1] S. Alikhani, D. Bakhshesh and H. Golmohammadi, Total coalitions in graphs (2022). arXiv: 2211.11590

[2] 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

[3] 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

[4] 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

[5] W. Goddard and M.A. Henning, Thoroughly dispersed colorings, J. Graph Theory 88 (2018) 174–191. https://doi.org/10.1002/jgt.22204

[6] 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

[7] 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.

[8] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Coalition graphs, Commun. Comb. Optim. 8 (2023) 423–430.

[9] 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

[10] 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

[11] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013).

[12] 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