On the Cayleyness of bipartite Kneser graphs

Document Type : Full Length Article

Author

Lorestan university

Abstract

For any given $n,k \in \mathbb{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,\dots, 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

On the Cayleyness of bipartite Kneser graphs

Keywords

Main Subjects

References

[1] B. Alspach, Cayley graphs, Topics in Algebraic Graph Theory, Cambridge University Press 2005.
[2] M.Arezoomand,Automorphismgroupofquasi-abeliansemi-Cayleygraphs,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, NewYork, 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) 223237.
[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, ProceedingsMathematical 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,BipartiteKnesergraphsareHamiltonian, Combinatorica37(2017)1206–1219.
Journal of Discrete Mathematics and Its Applications
Volume 9, Issue 3
September 2024
Pages 203-210

Files

History

  • Receive Date: 09 August 2024
  • Revise Date: 17 August 2024
  • Accept Date: 30 August 2024
  • Publish Date: 01 September 2024

Share

How to cite

Statistics