Secure coalitions in graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908676751622144 |
|---|---|
| author | Shetty, Swathi V., Sayinath Udupa N. Rakshith, B. R. |
| author_facet | Shetty, Swathi V., Sayinath Udupa N. Rakshith, B. R. |
| contents | A secure coalition in a graph $G$ consists of two disjoint vertex sets $V_1$ and $V_2$, neither of which is a secure dominating set, but whose union $V_1 \cup V_2$ forms a secure dominating set. A secure coalition partition ($sec$-partition) of $G$ is a vertex partition $π= \{V_1, V_2, \dots, V_k\}$ where each set $V_i$ 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 $V_j \in π$. 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 $V_1, V_2, \dots, V_k$ 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) \in \{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21170 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Secure coalitions in graphs Shetty, Swathi V., Sayinath Udupa N. Rakshith, B. R. Combinatorics 05A18, 05C69, 05C05, 05C35 A secure coalition in a graph $G$ consists of two disjoint vertex sets $V_1$ and $V_2$, neither of which is a secure dominating set, but whose union $V_1 \cup V_2$ forms a secure dominating set. A secure coalition partition ($sec$-partition) of $G$ is a vertex partition $π= \{V_1, V_2, \dots, V_k\}$ where each set $V_i$ 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 $V_j \in π$. 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 $V_1, V_2, \dots, V_k$ 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) \in \{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. |
| title | Secure coalitions in graphs |
| topic | Combinatorics 05A18, 05C69, 05C05, 05C35 |
| url | https://arxiv.org/abs/2511.21170 |