The number of shortest cycles and the chromatic uniqueness of a graph
Chung‐Piaw Teo, K.M. Koh · Journal of Graph Theory · 1992
Abstract For a graph G, let g(G) and σg(G) denote, respectively, the girth of G and the number of cycles of length g(G) in G. In this paper, we first obtain an upper bound for σg(G) and determine the structure of a 2‐connected graph G when σg(G) attains the bound. These extremal graphs are then more‐or‐less classified, but one case leads to an unsolved problem. The structural results are finally applied to show that certain families of graphs are chromatically unique.