2025/11/26 by Shetty, Swathi, Sayinath Udupa N. V., V., Sayinath Udupa N. +2
Computer Science · Economics, Econometrics and Finance · #05A18 #05C05 #05C35 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Voting Systems #Security in Wireless Sensor Networks
paper · pdf · doi:10.48550/arxiv.2511.21170
openalex publication_date 2025/11/26 · openalex created_date 2025/11/28 · openalex updated_date 2026/07/28
A secure coalition in a graph G consists of two disjoint vertex sets V1 and V2, neither of which is a secure dominating set, but whose union V1 ∪ V2 forms a secure dominating set. A secure coalition partition (sec-partition) of G is a vertex partition π= \V1, V2, …, Vk\ where each set Vi is either a secure dominating set consisting of a single vertex of degree n-1, or a set that is not a secure dominating set but forms a secure coalition with some other set Vj ∈ π. The maximum cardinality of a secure coalition partition of G is called the secure coalition number of G, denoted SEC(G). For every sec-partition π of a graph G, we associate a graph called the secure coalition graph of G with respect to π, denoted SCG(G,π), where the vertices of SCG(G,π) correspond to the sets V1, V2, …, Vk of π, and two vertices are adjacent in SCG(G,π) if and only if their corresponding sets in π form a secure coalition in G. In this study, we prove that every graph admits a sec-partition. Further, we characterize the graphs G with SEC(G) ∈ \1,2,n\ and all trees T with SEC(T) = n-1. Finally, we show that every graph G without isolated vertices is a secure coalition graph.