A stability result for girth‐regular graphs with even girth. Issue 1 (16th November 2021) - Kiss, György; Miklavič, Štefko; Szőnyi, Tamás
Abstract: Let Γ denote a finite, connected, simple graph. For an edge e of Γ let n ( e ) denote the number of girth cycles containing e . For a vertex v of Γ let e 1, e 2, …, e k be the set of edges incident to v ordered such that n ( e 1 ) ≤ n ( e 2 ) ≤ ⋯ ≤ n ( e k ) . Then ( n ( e 1 ), n ( e 2 ), …, n ( e k ) ) is called the signature of v . The graph Γ is said to be girth‐regular if all of its vertices have the same signature. Let Γ be a girth‐regular graph with girth g = 2 d and signature ( a 1, a 2, …, a k ) . It is known that in this case we have a k ≤ ( k − 1 ) d . In this paper we show that if a k = ( k − 1 ) d − ϵ for some nonnegative integer ϵ < k − 1, then ϵ = 0 . We also show that the above bound on ϵ is sharp by displaying examples of girth‐regular graphs with a k = ( k − 1 ) d − ( k − 1 ) for some values of k and d (in particular, for d = 2 ), and construct geometric examples where a k is not far from ( k − 1 ) d .