Edge Coalitions in Graphs

Abstract

Coalition concepts have been extensively studied in domination theory for vertex sets, whereas their edge counterparts have remained largely unexplored. Motivated by this, we introduce the notions of edge coalition, edge coalition partition, edge coalition number, and edge coalition graph. We prove that every graph admits an edge coalition partition and establish fundamental properties of these concepts. We derive sharp bounds for the edge coalition number, characterize graphs attaining its extremal values, and determine this parameter for several important graph classes, including complete graphs, complete bipartite graphs, paths, cycles, stars, trees, and unicyclic graphs. We further introduce the edge coalition graph associated with an edge coalition partition and investigate its structural properties. In particular, we characterize the edge coalition graphs of several graph classes and identify all self-edge coalition graphs. These results extend coalition theory from vertices to edges and provide a foundation for further research on edge coalition structures.

This submission is a revised and extended version of the manuscript previously available on arXiv in 2023. The current version contains improvements and additional results