no. 5
The super-connectivity of double generalized Petersen graphs
RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3659-3665

The super–connectivity of a graph G is the minimum number of vertices whose removal disconnects the graph without isolating a vertex. In this paper, we prove that the super–connectivity of double generalized Petersen graph DP(n, k) is equal to four when n ≥ 4, k ≥ 1 and n ≠ 2k.

DOI : 10.1051/ro/2022175
Classification : 05C40
Keywords: Connectivity, super–connectivity, double generalized Petersen graph 
@article{RO_2022__56_5_3659_0,
     author = {Ekinci, G\"ulnaz Boruzanli},
     title = {The super-connectivity of double generalized {Petersen} graphs},
     journal = {RAIRO. Operations Research},
     pages = {3659--3665},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {5},
     doi = {10.1051/ro/2022175},
     mrnumber = {4497837},
     zbl = {1502.05110},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022175/}
}
TY  - JOUR
AU  - Ekinci, Gülnaz Boruzanli
TI  - The super-connectivity of double generalized Petersen graphs
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 3659
EP  - 3665
VL  - 56
IS  - 5
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022175/
DO  - 10.1051/ro/2022175
LA  - en
ID  - RO_2022__56_5_3659_0
ER  - 
%0 Journal Article
%A Ekinci, Gülnaz Boruzanli
%T The super-connectivity of double generalized Petersen graphs
%J RAIRO. Operations Research
%D 2022
%P 3659-3665
%V 56
%N 5
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022175/
%R 10.1051/ro/2022175
%G en
%F RO_2022__56_5_3659_0
Ekinci, Gülnaz Boruzanli. The super-connectivity of double generalized Petersen graphs. RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3659-3665. doi: 10.1051/ro/2022175

[1] B. Alspach and J. Liu, On the hamilton connectivity of generalized petersen graphs. Discrete Math. 309 (2009) 5461–5473. | MR | Zbl | DOI

[2] F. T. Boesch, Synthesis of reliable networks - a survey. IEEE Trans. Reliab. 35 (1986) 240–246. | Zbl | DOI

[3] F. Boesch and R. Tindell, Circulants and their connectivities. J. Graph Theory 8 (1984) 487–499. | MR | Zbl | DOI

[4] G. Boruzanlı Ekinci and J. B. Gauci, On the reliability of generalized petersen graphs. Discrete Appl. Math. 252 (2019) 2–9. | MR | Zbl | DOI

[5] G. Boruzanlı Ekinci and J. B. Gauci, The super–connectivity of Kneser graphs. Discuss. Math. Graph Theory 39 (2019). | MR | Zbl | DOI

[6] Y. Chen, Y. Lin and W. Yan, The super-connectivity of kneser graph K G ( n , 3 ) Preprint (2021). | arXiv | MR | Zbl

[7] H. S. M. Coxeter, Self-dual configurations and regular graphs. Bull. Am. Math. Soc. 56 (1950) 413–455. | MR | Zbl | DOI

[8] A. Das, Determining number of generalized and double generalized petersen graph, in Conference on Algorithms and Discrete Applied Mathematics, Springer (2020) 131–140. | MR | Zbl | DOI

[9] B. J. Ebrahimi, N. Jahanbakht and E. S. Mahmoodian, Vertex domination of generalized petersen graphs. Discrete Math. 309 (2009) 4355–4361. | MR | Zbl | DOI

[10] A.-H. Esfahanian, Generalized measures of fault tolerance with application to N -cube networks. IEEE Trans. Comput. 38 (1989) 1586–1591. | DOI

[11] A.-H. Esfahanian and S. L. Hakimi, On computing a conditional edge-connectivity of a graph. Inf. Process. Lett. 27 (1988) 195–199. | MR | Zbl | DOI

[12] D. Ferrero and S. Hanusch, Component connectivity of generalized petersen graphs. Int. J. Comput. Math. 91 (2014) 1940–1963. | MR | Zbl | DOI

[13] L. Gao, X. Xu, J. Wang, D. Zhu and Y. Yang, The decycling number of generalized petersen graphs. Discrete Appl. Math. 181 (2015) 297–300. | MR | Zbl | DOI

[14] M. Ghasemi, Some results about the reliability of folded hypercubes. Bull. Malaysian Math. Sci. Soc. 44 (2021) 1093–1099. | MR | Zbl | DOI

[15] L. Guo, G. Su, W. Lin and J. Chen, Fault tolerance of locally twisted cubes. Appl. Math. Comput. 334 (2018) 401–406. | MR | Zbl

[16] F. Harary, Conditional connectivity. Networks 13 (1983) 347–357. | MR | Zbl | DOI

[17] L. Lin, L. Xu, S. Zhou and S.-Y. Hsieh, The extra, restricted connectivity and conditional diagnosability of split-star networks. IEEE Trans. Parallel Distrib. Syst. 27 (2016) 533–545. | DOI

[18] H. Qiao and J. Meng, On the hamilton laceability of double generalized petersen graphs, Discrete Math. 344 (2021) 112478. | MR | Zbl | DOI

[19] Y.-L. Qin, B. Xia and S. Zhou, Canonical double covers of generalized petersen graphs, and double generalized petersen graphs. J. Graph Theory 97 (2021) 70–81. | MR | Zbl | DOI

[20] Y Sakamoto, Hamilton cycles in double generalized petersen graphs. Preprint (2016). | arXiv | MR | Zbl

[21] X. Wang, All double generalized petersen graphs are hamiltonian. Discrete Math. 340 (2017) 3016–3019. | MR | Zbl | DOI

[22] J.-J. Wang and L.-H. Hsu, On the spanning connectivity of the generalized petersen graphs P ( n , 3 ) . Discrete Math. 341 (2018) 672–690. | MR | Zbl | DOI

[23] M. E. Watkins, A theorem on tait colorings with an application to the generalized petersen graphs. J. Comb. Theory 6 (1969) 152–164. | MR | Zbl | DOI

[24] J.-M. Xu, M. Lü, M. Ma and A. Hellwig, Super connectivity of line graphs. Inf. Process. Lett. 94 (2005) 191–195. | MR | Zbl | DOI

[25] W. Yang and J. Meng, Extraconnectivity of hypercubes. Appl. Math. Lett. 22 (2009) 887–891. | MR | Zbl | DOI

[26] W. Yang and J. Meng, Extraconnectivity of hypercubes (II). Australas. J. Comb. 47 (2010) 189–195. | MR | Zbl

[27] J.-X. Zhou and Y.-Q. Feng, Super-connected but not super edge-connected graphs. Inf. Process. Lett. 111 (2010) 22–25. | MR | Zbl | DOI

[28] J.-X. Zhou and Y.-Q. Feng, Cubic vertex-transitive non-Cayley graphs of order 8 p . Electron. J. Comb. 19 (2012) P53. | MR | Zbl | DOI

[29] J.-X. Zhou and Y.-Q. Feng, Cubic bi-Cayley graphs over abelian groups. Eur. J. Comb. 36 (2014) 679–693. | MR | Zbl | DOI

Cité par Sources :