Kissing numbers of regular graphs

DOI10.1007/S00493-021-4671-XMaRDI QIDQ6326133arXivFDO

Authors Maxime Fortier Bourque, Bram Petri

Publication date 27 September 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00493-021-4671-X

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

arXiv classification

math.CO math.MG

Abstract: 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.

This page was built for publication: Kissing numbers of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326133)