Abstract.
Let c(G) denote the number of cycles in G and let Q be
a class of graphs.
By cn(Q) we denote the minimum number c(G), where
G is a graph from Q with n vertices.
We consider the following classes of graphs:
-
Qk - the class of k-connected graphs,
-
Qk,d - the class of k-connected graphs with minimum
degree d,
-
Qk,d,D - the class of k-connected graphs with minimum
degree d and maximum degree D.
We give polynomial upper bounds on cn(Qk) and
cn(Qk,d), and lower bounds on
cn(Qk,d) and
cn(Qk,d,D).