A stability result for girth‐regular graphs with even girth. Issue 1 (16th November 2021)

• Record Type: Journal Article
• Authors: Kiss, György; Miklavič, Štefko; Szőnyi, Tamás
• Is Part Of: Journal of graph theory. Volume 100:Issue 1(2022)
• Page Start: 163
• Page End: 181
• Publication Date: 2021-11-16
• Subjects: girth cycle -- girth‐regular graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22770
• Languages: English
• ISSNs: 0364-9024

Abstract

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 .