- Tytuł:
- Lower Bound on the Number of Hamiltonian Cycles of Generalized Petersen Graphs
- Autorzy:
-
Lu, Weihua
Yang, Chao
Ren, Han - Powiązania:
- https://bibliotekanauki.pl/articles/32083755.pdf
- Data publikacji:
- 2020-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
generalized Petersen graph
Hamiltonian cycle
partition number
1-factor - Opis:
- In this paper, we investigate the number of Hamiltonian cycles of a generalized Petersen graph $ P(N, k) $ and prove that $ \Psi(P(N,3)) \ge N \cdot \alpha_N $, where $ \Psi (P(N, 3)) $ is the number of Hamiltonian cycles of $P(N, 3)$ and $ \alpha_N $ satisfies that for any $ \epsilon > 0 $, there exists a positive integer $M$ such that when $ N > M $, $ ((1− \epsilon ) \frac{ (1−r^3) }{6r^3+5r^2+3) }( 1/r )^{N+2} < \alpha_N < ( (1+ɛ) \frac{ (1−r^3) }{6r^3+5r^2+3) }( 1/r )^{N+2} $, where $ 1/r = \text{max} \{ | \frac{1}{r_j} | : j=1,2,…,6 \} $, and each $ r_j $ is a root of equation $ x^6 + x^5 + x^3 − 1 = 0 $, $ r \approx 0.782 $. This shows that $ \Psi (P (N, 3) $ is exponential in $N$ and also deduces that the number of 1-factors of $ P(N, 3)$ is exponential in $N$.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 297-305
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł