تقرير
Lights Out On A Random Graph
| العنوان: | Lights Out On A Random Graph |
|---|---|
| المؤلفون: | Forrest, Bradley, Manno, Nicole |
| المصدر: | The PUMP Journal of Undergraduate Research, 5, 165-175 (2022) |
| سنة النشر: | 2021 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Mathematics - Probability, 05C57, 05C80, 60C99 |
| الوصف: | We consider the generalized game Lights Out played on a graph and investigate the following question: for a given positive integer $n$, what is the probability that a graph chosen uniformly at random from the set of graphs with $n$ vertices yields a universally solvable game of Lights Out? When $n \leq 11$, we compute this probability exactly by determining if the game is universally solvable for each graph with $n$ vertices. We approximate this probability for each positive integer $n$ with $n \leq 100$ by applying a Monte Carlo method using 1,000,000 trials. We also perform the analogous computations for connected graphs. Comment: 10 pages, 1 figure. The first version incorrectly stated that the number of unlabeled graphs with n vertices was known up to n=87. It is known at least up n=140, see reference 5. Consequently, we extended our results from n=87 to n=100, which required improving our algorithm. All results in the second version were obtained using the new code |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2108.07349 |
| رقم الأكسشن: | edsarx.2108.07349 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |