Premium
The number of shortest cycles and the chromatic uniqueness of a graph
Author(s) -
Teo C. P.,
Koh K. M.
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160103
Subject(s) - combinatorics , mathematics , chromatic scale , graph , uniqueness , upper and lower bounds , discrete mathematics , girth (graph theory) , mathematical analysis
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.