Diameter of generalized Petersen graphs
| Autor: | Loudiki, Laila, Kchikech, Mustapha, Essaky, El Hassan |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Due to their broad application to different fields of theory and practice, generalized Petersen graphs $GPG(n,s)$ have been extensively investigated. Despite the regularity of generalized Petersen graphs, determining an exact formula for the diameter is still a difficult problem. In their paper, Beenker and Van Lint have proved that if the circulant graph $C_n(1,s)$ has diameter $d$, then $GPG(n,s)$ has diameter at least $d+1$ and at most $d+2$. In this paper, we provide necessary and sufficient conditions so that the diameter of $GPG(n,s)$ is equal to $d+1,$ and sufficient conditions so that the diameter of $GPG(n,s)$ is equal to $d+2.$ Afterwards, we give exact values for the diameter of $GPG(n,s)$ for almost all cases of $n$ and $s.$ Furthermore, we show that there exists an algorithm computing the diameter of generalized Petersen graphs with running time $O$(log$n$). Comment: We found much general results we want to add to this work |
| Databáze: | arXiv |
| Externí odkaz: |
|