A stability result for girth-regular graphs with even girth

Let Gamma denote a finite, connected, simple graph. For an edge e of Gamma let n ( e ) denote the number of girth cycles containing e. For a vertex v of Gamma let { e 1 , e 2 , horizontal ellipsis , e k } be the set of edges incident to v ordered such that n ( e 1 ) <= n ( e 2 ) <= MIDLINE HORIZONTAL ELLIPSIS <= n ( e k ). Then ( n ( e 1 ) , n ( e 2 ) , horizontal ellipsis , n ( e k ) ) is called the signature of v. The graph Gamma is said to be girth-regular if all of its vertices have the same signature. Let Gamma be a girth-regular graph with girth g = 2 d and signature ( a 1 , a 2 , horizontal ellipsis , 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 - epsilon for some nonnegative integer epsilon < k - 1, then epsilon = 0. We also show that the above bound on epsilon 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.

Automated summary

This paper discusses the characteristics of finite, connected, simple graphs and the properties of girth-regular graphs. By proving the relationship of characteristic values under certain conditions, a specific range of characteristic values of girth-regular graphs is obtained. In addition, examples of girth-regular graphs are presented.