Edge coalitions in graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, Faculty of Sciences Payame Noor University, Tehran, Iran

2 Department of Mathematics, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran

3 Department of Mathematics, Faculty of Mathematical Sciences, University of Tafresh, Tafresh, Iran

10.22108/toc.2026.150035.2385

Abstract

Coalition theory for vertex sets has been extensively studied, whereas its edge counterpart has received much less attention. In this paper, we introduce edge coalitions, edge coalition partitions, the edge coalition number, and edge coalition graphs. We prove that every graph with at least one edge admits an edge coalition partition and establish bounds on the edge coalition number, including lower bounds for complete and complete bipartite graphs. We characterize trees and unicyclic graphs \(G\) satisfying \(EC(G)=|E(G)|\). For connected graphs that are neither trees nor unicyclic, we reduce the problem to a line-graph condition; a direct structural characterization in terms of \(G\) remains open. We also determine the edge coalition number for several standard graph families, including paths, cycles, stars, and complete graphs of small order. In addition, we establish structural properties of edge coalition graphs and characterize all connected self-edge coalition graphs. These results extend coalition theory from vertices to edges and provide a foundation for further study of edge coalition structures.

Keywords

Main Subjects


[1] S. Alikhani, D. Bakhshesh, H. Golmohammadi and E. V. Konstantinova, Connected coalitions in graphs, Discuss. Math. Graph Theory, 44 no. 4 (2024) 1551–1566.
[2] S. Arumugam and S. Velammal, Edge domination in graphs, Taiwanese J. Math., 2 no. 2 (1998) 173–179.
[3] J. Baste, M. F¨urst, M. A. Henning, E. Mohr and D. Rautenbach, Domination versus edge domination, Discrete Appl. Math., 285 (2020) 343–349.
[4] J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, 244, Springer, New York, 2008.
[5] 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 no. 2 (2020) 653–659.
[6] 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 no. 3 (2021) 442–453.
[7] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Coalition graphs, Commun. Comb. Optim., 8 no. 2 (2023) 423–430.
[8] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Coalition graphs of paths, cycles and trees, Discuss. Math. Graph Theory, 43 no. 4 (2023) 931–946.
[9] M. A. Henning and D. A. Mojdeh, Double coalitions in graphs, Bull. Malays. Math. Sci. Soc., 48 no. 2 (2025) Article 51 pp. 19.
[10] M. A. Henning and D. A. Mojdeh, Double coalitions in regular graphs, Graphs Combin., 41 no. 4 (2025), Article 74 pp. 19.
[11] D. B. West, Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
[12] F. Yang, Q. Sun and C. Zhang, Characterizations of graphs with equal vertex and coalition number, Discrete Appl. Math., 381 (2026) 112–119.
[13] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math., 38 no. 3 (1980) 364–372.
[14] B. Zelinka, Edge-domatic number of a graph, Czechoslovak Math. J., 33(108) no. 1 (1983) 107–110.

Articles in Press, Accepted Manuscript
Available Online from 29 October 2026
  • Receive Date: 04 August 2026
  • Revise Date: 28 October 2026
  • Accept Date: 29 October 2026
  • Published Online: 29 October 2026