On the distance transitivity of the bipartite Kneser graphs

Document Type : Research Paper

Author

Department of Mathematics, Iranmehr Univertsity, Kordestan, Iran

Abstract

In this paper, we study a family of graphs related to Johnson graphs, known as bipartite Kneser graphs. Let n and k be integers such that n>k 1≥. We denote by H(n, k) the bipartite Kneser graph, whose vertex set consists of all k-subsets and (n - k)-subsets of the set [n] = {1, 2, ..., n}, where two vertices are adjacent if and only if one is a subset of the other. Mirafzal (S. M. Mirafzal, The automorphism group of the bipartite Kneser graph, Proc. Indian Acad. Sci. (Math. Sci.), (2019) 129 (34), proved that the automorphism group of the bipartite Kneser graph H(n, k) is isomorphic to Sym ([n])×Z2. In this paper, we investigate the distance-transitivity and the diameter of the bipartite Kneser graphs. It is known that H(n, k) is distance-transitive precisely when k=1 or n=2k+1. In this work, we provide new structural proofs of these cases directly within the bipartite Kneser framework, and we determine the diameter of H(n, k) for various ranges of n and k.

Keywords

Main Subjects


[1] B. Alspach, Johnson graphs are Hamiltonian-connected, Ars Math. Contemp. 6 (2013), 21–23.
[2] N. L. Biggs, Algebraic Graph Theory (Second edition), New York, Cambridge Mathematical Library, Cambridge University Press, 1993.
[3] A. E. Brouwer, A. M. Cohn, A. Neumaer, Distance regular graphs, New York: Springer-Verlag, 1980. 
[4] Y. C. Chen, Kneser Graphs Are Hamiltonian For n ≥ 3k, J Comb Theory B. 80 (2000), 69–79.
[5] D. Cvetkovic, P. Rowlinson, S. Simic, An introduction to the theory of graph spectra, New York, Cambridge Mathematical Library, Cambridge University Press, 2001.
[6] C. Dalfo, M. A. Fiol, M. Mitjana, On Middle Cube Graphs. Electron, J. Graph Theory Appl. 13 (2015), 133–145.
[7] G. A. Jones, Automorphisms and regular embedings of merged Johnson graphs, European J. Combin. 26 (2005), 417–435.
[8] A. Hiraki, A characterization of the doubled Grassmann graphs, the doubled Odd graphs, and the Odd graphs by strongly closed subgraphs, European J. Combin 24 (2003), 161–171.
[9] J. S. Kim, E, Cheng, L. Liptak, H. O. Lee, Embedding hypercubes, rings, and odd graphs into hyper-stars, Int. J. Comput. Math. 86 (2009), 771–778.
[10] S. M. Mirafzal, The automorphism group of the bipartite Kneser graph, Proc. Indian Acad. Sci. (Math. Sci). 129 (34) (2019).
[11] S. M. Mirafzal, A. Zafri, Some algebraic properties of bipartite Kneser graphs, Ars Comb. 153 (2020), 3–13 .
[12] T. M¨utze, P, Su, Bipartite Kneser graphs are Hamiltonian, Electron. Notes Discrete Math. 49 (2015), 259–267.
[13] D. K. Ray-Chaudhuri, AP, Sprague, Characterization of projective incidence structures, Geom. Dedicata. 5 (1976), 361–376.
[14] M. Ziaee, On the automorphism group of doubled Grassmann graphs Proc. Indian Acad. Sci. (Math. Sci).130 (64) (2020).