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

Year 2021, Volume: 4 Issue: 4, 251 - 257, 01.12.2021

Gülnaz Boruzanlı Ekinci

https://doi.org/10.33401/fujma.975352

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] Y. Alavi, M. Behzad, P. Erdos, D. R. Lick, Double vertex graphs, J. Comb. Inf. Syst. Sci., 16(1) (1991), 37-50.
• [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] Y. Alavi, D. R. Lick, J. Liu, Survey of double vertex graphs, Graphs Combin., 18(4) (2002), 709-715.
• [4] T. Rudolph, Constructing physically intuitive graph invariants, (2002), arXiv:quant-ph/0206068.
• [5] K. Audenaert, C. Godsil, G. Royle, T. Rudolph, Symmetric squares of graphs, J. Combin. Theory Ser. B, 97(1) (2007), 74-90.
• [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] 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] L. Adame, L. M. Rivera, A. L. Trujillo-Negrete, Hamiltonicity of token graphs of some join graphs, Symmetry, 13(6) (2021), 1076.
• [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] J. Deepalakshmi, G. Marimuthu, Characterization of token graphs, J. Eng. Technol., 6 (2017), 310-317.
• [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] P. Jimenez-Sep´ulveda, L. M. Rivera, Independence numbers of some double vertex graphs and pair graphs, (2018), arXiv:1810.06354 [math.CO].
• [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] 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] F. Harary, Conditional connectivity, Networks, 13(3) (1983), 347-357.
• [16] F. Boesch, R. Tindell, Circulants and their connectivities, J. Graph Theory, 8(4) (1984), 487-499.
• [17] W. Yang, J. Meng, Extraconnectivity of hypercubes, Appl. Math. Lett., 22(6) (2009), 887-891.
• [18] W. Yang, J. Meng, Extraconnectivity of hypercubes (II), Australas. J. Comb., 47 (2010), 189-196.
• [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] L. Guo, C. Qin, X. Guo, Super connectivity of Kronecker products of graphs, Inform. Process. Lett., 110 (16) (2010), 659-661.
• [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] J. Lea˜nos, A. L. Trujillo-Negrete, The connectivity of token graphs, Graphs Combin., 34(4) (2018), 777-790.
• [23] J. Lea˜nos, C. Ndjatchi, The edge-connectivity of token graphs, Graphs Combin., 37(3) (2021), 1013-1023.
• [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] G. B. Ekinci, J. B. Gauci, The super-connectivity of Johnson graphs, Discrete Math. Theor. Comput. Sci., 22(1) (2020).