Coalition Graphs of Complete Bipartite Graphs

Abstract

A coalition in a graph G= (V, E) consists of two disjoint, non-dominating vertex subsets whose union forms a dominating set, and a coalition graph is constructed from a coalition partition by representing each part as a vertex and connecting two parts if they form a coalition. This paper provides a comprehensive structural analysis of coalition graphs derived from complete bipartite graphs Kr,s, a fundamental graph class with broad applications in resource allocation, scheduling, and two-layered network systems. We completely characterize all possible coalition graphs for star graphs K1,s, proving that they are strictly limited to three isomorphism types: K1​, K2​, or the disjoint union K1∪K2​, thereby revealing the restrictive coalition behavior imposed by the hub-and-spoke topology. For general complete bipartite graphs Kr,s, we establish several key structural results: the coalition number c(Kr,s) is exactly r+s, attained by the singleton partition; the independence number of any coalition graph derived from Kr,s​ is at least  max{r,s}; and the maximum degree satisfies Δ(CG (Kr,s;π))≤max{r,s}+1 for any coalition partition π. These findings provide a complete theoretical description of coalition structures within bipartite frameworks, extending the known families of coalition graphs beyond paths, cycles, and trees. By bridging structural properties with the membership requirements of complete bipartite graphs, this work establishes a robust mathematical foundation for addressing the inverse problem of coalition graphs and opens new directions for exploring higher-order multipartite structures and their computational complexities