On the Cayleyness of bipartite Kneser graphs

Mirafzal, Seyed Morteza

doi:10.22061/jdma.2024.11145.1080

On the Cayleyness of bipartite Kneser graphs

Document Type : Full Length Article

Author

Seyed Morteza Mirafzal

Department of Pure Mathematics, Lorestan University, Khorramabad, I. R. Iran

10.22061/jdma.2024.11145.1080

Abstract

For any given n,k ∈ N with 2k < n, the bipartite Kneser graph H(n, k) is defined as the graph whose vertex set is the family of k-subsets and (n-k)-subsets of [n] = {1, 2,..., n} in which any two vertices are adjacent if and only if one of them is a subset of the other. In this paper, we study some algebraic properties of the bipartite Kneser graph H(n, k). In particular, we determine the values of n,k for which the bipartite Kneser graph H(n,k) is a Cayley graph.

Graphical Abstract

Keywords

Main Subjects

Graph and Hypergraph Theory

References

[1] B. Alspach, Cayley graphs, Topics in Algebraic Graph Theory, Cambridge University Press 2005.

[2] M. Arezoomand, Automorphism group of quasi-abelian semi-Cayley graphs, J. Disc. Math. Appl. 8 (2023) 43–48.

[3] N. L. Biggs, Some odd graph theory. Ann. New York Acad. Sci. 319 (1979) 71-81.

[4] N. L. Biggs, Algebraic Graph Theory (Second edition), Cambridge Mathematical Library (Cambridge University Press; Cambridge), 1993.

[5] J. D. Dixon, B. Mortimer, Permutation Groups, Graduate Texts in Mathematics, Springer-Verlag, New York, 1996.

[6] C. D. Godsil, More odd graph theory, Discrete Mathematics 32 (1980) 205–207.

[7] C. D. Godsil, G. Royle, Algebraic Graph Theory, Springer, 2001.

[8] R. Hammack, W. Imrich, S. Klavzar, Handbook of Product Graphs, second edition, CRC press 2011.

[9] W. Kantor, k-homogeneous groups, Math. Z. 124 (1972) 261–265.

[10] A. Khalilipour, M. Ghorbani, Perfect state transfer on Cayley graphs over groups, J. Disc. Math. Appl. 9(1) (2024) 49–62.

[11] J. S. Kim, E. Cheng, L. Liptak, H. O. Lee, Embedding hypercubes, rings and odd graphs into hyper-stars, International Journal of Computer Mathematics (2009) 86 (5) 771–778.

[12] S. Mehry, Ramanujan Cayley graphs on sporadic groups, J. Disc. Math. Appl. 8(4) (2023) 223-237.

[13] S. M. Mirafzal, On the automorphism groups of regular hyperstars and folded hyperstars, Ars Comb. (2015) 75–86. [14] S. M. Mirafzal, Some other algebraic properties of folded hypercubes, Ars Comb. 124 (2016) 153–159.

[15] S. M. Mirafzal, More odd graph theory from another point of view, Discrete Mathematics 341 (2018) 217-220.

[16] S. M. Mirafzal, The automorphism group of the bipartite Kneser graph, Proceedings Mathematical Sciences (2019) doi.org/10.1007/s12044-019-0477-9.

[17] S. M. Mirafzal, M. Ziaee, Some algebraic aspects of enhanced Johnson graphs, Acta Math. Univ. Comenianae 88(2) (2019) 257–266.

[18] S. M. Mirafzal, A. Zafari, Some algebraic properties of bipartite Kneser graphs, Ars Comb. 153 (2020) 3–13.

[19] S. M. Mirafzal, On the automorphism groups of connected bipartite irreducible graphs. Proc. Math. Sci. (2020). https://doi.org/10.1007/s12044-020-0589-1

[20] S. M. Mirafzal, Cayley properties of the line graphs induced by consecutive layers of the hypercube, Bull. Malaysian Math. Sci. 44 (2021) 1309–1326 https://doi.org/10.1007/s40840-020-01009-3.

[21] S. M. Mirafzal, A note on the automorphism groups of Johnson graphs, Ars Comb. 154 (2021) 245–255 (Available from: arXiv: 1702.02568v4).

[22] S. M. Mirafzal, M. Ziaee, A note on the automorphism group of the Hamming graph, Transactions on Combinatorics 10 (2021) 129–136.

[23] S. M. Mirafzal, The automorphism group of the Andrásfai graph, Discrete Math. Lett. 10 (2022) 60–63.

[24] S. M. Mirafzal, Some remarks on the square graph of the hypercube, Ars Mathematica Contemporanea 23(2) (2023) 2–6.

[25] S. M. Mirafzal, On the automorphism groups of us-Cayley graphs, The Art of Discrete and Applied Mathematics (2023) doi: https://doi.org/10.26493/2590-9770.1624.a3d.

[26] S. M. Mirafzal, Some algebraic properties of the subdivision graph of a graph, Communications in Combinatorics and Optimization (2023) 297–307.

[27] T. M. Mütze, P. Su, Bipartite Kneser graphs are Hamiltonian, Combinatorica 37 (2017) 1206–1219.