General sharp upper bounds on the transversal coalition number

Blázsik, Zoltán ✉ [Blázsik, Zoltán (kombinatorika, gr...), szerző] Bolyai Intézet (Matematikai Intézet) (SZTE / TTIK)

Angol nyelvű Szakcikk (Folyóiratcikk) Tudományos
Megjelent: DISCRETE APPLIED MATHEMATICS 0166-218X 1872-6771 378 pp. 384-391 2026
  • SJR Scopus - Applied Mathematics: Q2
Azonosítók
Támogatások:
  • ÚNKP(ÚNKP-23-4-SZTE-628)
  • (SNN 132625) Támogató: OTKA
Let $\mathcal{H}(V,E)$ be a finite hypergraph with vertex set $V$ and edge set $E$ such that every hyperedge is non-empty. Two disjoint sets $A,B\subset V$ form a transversal coalition in $\mathcal{H}$, if none of them is a transversal, but their union $A\cup B$ is a transversal. A vertex partition $\Psi=\{V_1,V_2,\dots,V_p\}$ is a transversal coalition partition, if none of the partition classes is a transversal, meanwhile for every $i\in\{1,2,\dots,p\}$ there exists a distinct $j\in\{1,2,\dots,p\}$ such that $V_i$ and $V_j$ form a transversal coalition. The maximum cardinality of a transversal coalition partition of $\mathcal{H}$ is the transversal coalition number of $\mathcal{H}$ and denoted by $C_{\tau}(\mathcal{H})$. We generalize the previous upper bounds of Barát and Blázsik on the total coalition number by using the open neighborhood hypergraph construction. This connection was recently pointed out by Henning and Yeo and they proved similar upper bounds on the transversal coalition number for $k$-uniform hypergraphs. We also generalize their results by omitting the uniformity constraint. We give upper bounds in terms of the minimum and maximum size of the hyperedges. We further investigate this optimal case and study the transversal coalition graph. We prove that the possible optimal transversal coalition graphs are exactly the same as the optimal total coalition graphs.We show that every graph can be realised as a transversal coalition graph.
Hivatkozás stílusok: IEEEACMAPAChicagoHarvardCSLMásolásNyomtatás
2026-01-13 07:51