Hopping Forcing Number in Random $d$-regular 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_ | 1866910645238104064 |
|---|---|
| author | Pralat, Pawel Singh, Harjas |
| author_facet | Pralat, Pawel Singh, Harjas |
| contents | Hopping forcing is a single player combinatorial game in which the player is presented a graph on $n$ vertices, some of which are initially blue with the remaining vertices being white. In each round $t$, a blue vertex $v$ with all neighbours blue may hop and colour a white vertex blue in the second neighbourhood, provided that $v$ has not performed a hop in the previous $t-1$ rounds. The objective of the game is to eventually colour every vertex blue by repeatedly applying the hopping forcing rule. Subsequently, for a given graph $G$, the hopping forcing number is the minimum number of initial blue vertices that are required to achieve the objective.
In this paper, we study the hopping forcing number for random $d$-regular graphs. Specifically, we aim to derive asymptotic upper and lower bounds for the hopping forcing number for various values of $d \geq 2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08380 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hopping Forcing Number in Random $d$-regular Graphs Pralat, Pawel Singh, Harjas Combinatorics Hopping forcing is a single player combinatorial game in which the player is presented a graph on $n$ vertices, some of which are initially blue with the remaining vertices being white. In each round $t$, a blue vertex $v$ with all neighbours blue may hop and colour a white vertex blue in the second neighbourhood, provided that $v$ has not performed a hop in the previous $t-1$ rounds. The objective of the game is to eventually colour every vertex blue by repeatedly applying the hopping forcing rule. Subsequently, for a given graph $G$, the hopping forcing number is the minimum number of initial blue vertices that are required to achieve the objective. In this paper, we study the hopping forcing number for random $d$-regular graphs. Specifically, we aim to derive asymptotic upper and lower bounds for the hopping forcing number for various values of $d \geq 2$. |
| title | Hopping Forcing Number in Random $d$-regular Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.08380 |