Kissing Numbers of Regular Graphs - Sorbonne Université Accéder directement au contenu
Article Dans Une Revue Combinatorica Année : 2021

Kissing Numbers of Regular Graphs

Résumé

We prove a sharp upper bound on the number of shortest cycles contained inside any connected graph in terms of its number of vertices, girth, and maximal degree. Equality holds only for Moore graphs, which gives a new characterization of these graphs. In the case of regular graphs, our result improves an inequality of Teo and Koh. We also show that a subsequence of the Ramanujan graphs of Lubotzky-Phillips-Sarnak have super-linear kissing numbers.
Fichier principal
Vignette du fichier
1909.12817.pdf (961.17 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03463058 , version 1 (02-12-2021)

Identifiants

Citer

Maxime Fortier, Bram Petri. Kissing Numbers of Regular Graphs. Combinatorica, 2021, ⟨10.1007/s00493-021-4671-x⟩. ⟨hal-03463058⟩
24 Consultations
45 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More