Gromov hyperbolicity of Johnson and Kneser graphs Articles uri icon

publication date

  • May 2024

start page

  • 661

end page

  • 686

issue

  • 3

volume

  • 98

International Standard Serial Number (ISSN)

  • 0001-9054

Electronic International Standard Serial Number (EISSN)

  • 1420-8903

abstract

  • The concept of Gromov hyperbolicity is a geometric concept that leads to a rich general theory. Johnson and Kneser graphs are interesting combinatorial graphs defined from systems of sets. In this work we compute the precise value of the hyperbolicity constant of every Johnson graph. Also, we obtain good bounds on the hyperbolicity constant of every Kneser graph, and in many cases, we even compute its precise value.

subjects

  • Mathematics

keywords

  • johnson graphs; kneser graphs; gromov hyperbolicity; geodesics