Girth-regular graphs

Authors

  • Primož Potočnik University of Ljubljana, Slovenia and Institute of Mathematics, Physics, and Mechanics, Slovenia
  • Janoš Vidali University of Ljubljana, Slovenia

DOI:

https://doi.org/10.26493/1855-3974.1684.b0d

Keywords:

Graph, girth-regular, cubic, girth

Abstract

We introduce a notion of a girth-regular graph as a k-regular graph for which there exists a non-descending sequence (a1, a2, …, ak) (called the signature) giving, for every vertex u of the graph, the number of girth cycles the edges with end-vertex u lie on. Girth-regularity generalises two very different aspects of symmetry in graph theory: that of vertex transitivity and that of distance-regularity. For general girth-regular graphs, we give some results on the extremal cases of signatures. We then focus on the cubic case and provide a characterisation of cubic girth-regular graphs of girth up to 5.

Published

2019-11-04

Issue

Section

Articles