Details

Autor(en) / Beteiligte

• Kiss, György
• Miklavič, Štefko
• Szőnyi, Tamás

Titel

A stability result for girth‐regular graphs with even girth

Ist Teil von

• Journal of graph theory, 2022-05, Vol.100 (1), p.163-181

Ort / Verlag

Hoboken: Wiley Subscription Services, Inc

Erscheinungsjahr

2022

Quelle

Wiley Online Library Core Title

Beschreibungen/Notizen

• 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.