$k$-Coalitions in Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |