The Super-Connectivity of the Double Vertex Graph of Complete Bipartite Graphs

Abstract

Let $ G=(V,E) $ be a graph. The double vertex graph $F_2(G)$ of $ G $ is the graph whose vertex set consists of all $ 2 $-subsets of $ V(G) $ such that two vertices are adjacent in $ F_2(G) $ if their symmetric difference is a pair of adjacent vertices in $ G $. The super--connectivity of a connected graph is the minimum number of vertices whose removal results in a disconnected graph without an isolated vertex. In this paper, we determine the super--connectivity of the double vertex graph of the complete bipartite graph $ K_{m,n} $ for $ m\geq 4 $ where $ n\geq m+2 $.

Keywords

• Connectivity
• Double vertex graph
• Super connectivity
• Token graph

References

1. [1] Y. Alavi, M. Behzad, P. Erdos, D. R. Lick, Double vertex graphs, J. Comb. Inf. Syst. Sci., 16(1) (1991), 37-50.
2. [2] Y. Alavi, M. Behzad, J. E. Simpson, Planarity of Double Vertex Graphs, Graph theory, combinatorics, algorithms, and applications (San Francisco, CA) (1991), 472-485.
3. [3] Y. Alavi, D. R. Lick, J. Liu, Survey of double vertex graphs, Graphs Combin., 18(4) (2002), 709-715.
4. [4] T. Rudolph, Constructing physically intuitive graph invariants, (2002), arXiv:quant-ph/0206068.
5. [5] K. Audenaert, C. Godsil, G. Royle, T. Rudolph, Symmetric squares of graphs, J. Combin. Theory Ser. B, 97(1) (2007), 74-90.
6. [6] R. Fabila-Monroy, D. Flores-Pe˜naloza, C. Huemer, F. Hurtado, J. Urrutia, D. R. Wood, Token graphs, Graphs Combin., 28(3) (2012), 365-380.
7. [7] L. Adame, L. M. Rivera, A. L. Trujillo-Negrete, Hamiltonicity of the double vertex graph and the complete double vertex graph of some join graphs, (2020), arXiv:2007.00115 [math.CO].
8. [8] L. Adame, L. M. Rivera, A. L. Trujillo-Negrete, Hamiltonicity of token graphs of some join graphs, Symmetry, 13(6) (2021), 1076.

9. [9] H. de Alba, W. Carballosa, J. Lea˜nos, L. M. Rivera, Independence and matching numbers of some token graphs, Australas. J. Combin., 76 (2020), 387-403.
10. [10] J. Deepalakshmi, G. Marimuthu, Characterization of token graphs, J. Eng. Technol., 6 (2017), 310-317.
11. [11] J. Deepalakshmi, G. Marimuthu, A. Somasundaram, S. Arumugam, On the 2-token graph of a graph, AKCE Int. J. Graphs Comb., 17(1) (2019), 265-268.
12. [12] P. Jimenez-Sep´ulveda, L. M. Rivera, Independence numbers of some double vertex graphs and pair graphs, (2018), arXiv:1810.06354 [math.CO].
13. [13] S. S. Kumar, R. Sundareswaran, M. Sundarakannan, On Zagreb indices of double vertex graphs, TWMS J. Appl. Eng. Math., 10(4) (2020), 1096-1104.
14. [14] J. G. Soto, J. Lea˜nos, L. M. R´ıos-Castro, L. M. Rivera, The packing number of the double vertex graph of the path graph, Discrete Appl. Math., 247 (2018), 327-340.
15. [15] F. Harary, Conditional connectivity, Networks, 13(3) (1983), 347-357.
16. [16] F. Boesch, R. Tindell, Circulants and their connectivities, J. Graph Theory, 8(4) (1984), 487-499.
17. [17] W. Yang, J. Meng, Extraconnectivity of hypercubes, Appl. Math. Lett., 22(6) (2009), 887-891.
18. [18] W. Yang, J. Meng, Extraconnectivity of hypercubes (II), Australas. J. Comb., 47 (2010), 189-196.
19. [19] G. B. Ekinci, A. Kırlangic¸, Super connectivity of Kronecker product of complete bipartite graphs and complete graphs, Discrete Math., 339(7) (2016), 1950-1953.
20. [20] L. Guo, C. Qin, X. Guo, Super connectivity of Kronecker products of graphs, Inform. Process. Lett., 110 (16) (2010), 659-661.
21. [21] M. L¨u, C. Wu, G.-L. Chen, C. Lv, On super connectivity of Cartesian product graphs, Networks, 52(2) (2008), 78-87.
22. [22] J. Lea˜nos, A. L. Trujillo-Negrete, The connectivity of token graphs, Graphs Combin., 34(4) (2018), 777-790.
23. [23] J. Lea˜nos, C. Ndjatchi, The edge-connectivity of token graphs, Graphs Combin., 37(3) (2021), 1013-1023.
24. [24] R. Fabila-Monroy, J. Lea˜nos, A. L. Trujillo-Negrete, On the connectivity of token graphs of trees, (2020), arXiv:2004.14526 [math.CO].
25. [25] G. B. Ekinci, J. B. Gauci, The super-connectivity of Johnson graphs, Discrete Math. Theor. Comput. Sci., 22(1) (2020).