$k$-Coalitions in Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916320681918464 |
|---|---|
| author | Jafari, Abbas Alikhani, Saeid Bakhshesh, Davood |
| author_facet | Jafari, Abbas Alikhani, Saeid Bakhshesh, Davood |
| contents | In this paper, we propose and investigate the concept of $k$-coalitions in graphs, where $k\ge 1$ is an integer. A $k$-coalition refers to a pair of disjoint vertex sets that jointly constitute a $k$-dominating set of the graph, meaning that every vertex not in the set has at least $k$ neighbors in the set. We define a $k$-coalition partition of a graph as a vertex partition in which each set is either a $k$-dominating set with exactly $k$ members or forms a $k$-coalition with another set in the partition. The maximum number of sets in a $k$-coalition partition is called the $k$-coalition number of the graph represented by $C_k(G)$. We present fundamental findings regarding the properties of $k$-coalitions and their connections with other graph parameters. We obtain the exact values of $2$-coalition number of some specific graphs and also study graphs with large $2$-coalition number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09332 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | $k$-Coalitions in Graphs Jafari, Abbas Alikhani, Saeid Bakhshesh, Davood Combinatorics 05C69 In this paper, we propose and investigate the concept of $k$-coalitions in graphs, where $k\ge 1$ is an integer. A $k$-coalition refers to a pair of disjoint vertex sets that jointly constitute a $k$-dominating set of the graph, meaning that every vertex not in the set has at least $k$ neighbors in the set. We define a $k$-coalition partition of a graph as a vertex partition in which each set is either a $k$-dominating set with exactly $k$ members or forms a $k$-coalition with another set in the partition. The maximum number of sets in a $k$-coalition partition is called the $k$-coalition number of the graph represented by $C_k(G)$. We present fundamental findings regarding the properties of $k$-coalitions and their connections with other graph parameters. We obtain the exact values of $2$-coalition number of some specific graphs and also study graphs with large $2$-coalition number. |
| title | $k$-Coalitions in Graphs |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2407.09332 |