General sharp upper bounds on the total coalition number

Barát, János and Blázsik, Zoltán (2024) General sharp upper bounds on the total coalition number. DISCUSSIONES MATHEMATICAE GRAPH THEORY. ISSN 1234-3099

Preview

Text 2301.09979v3.pdf Available under License Creative Commons Attribution. Download (771kB) | Preview

Abstract

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 Ψ = {C1, C2, ... , Ck} 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 Ci and Cj form a total coalition. The maximum cardinality of a total coalition partition of G is the total coalition number of G and denoted by T C(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.

Actions (login required)

Edit Item