The Minimum Number of Cycles in Graphs with Given Cycle Rank and Small Connectivity

Abstract

The cycle rank, $r(G)$, of a graph $G=(V,E)$ is given by $r(G)=|E|–|V|+1$. Let $f(k,r)$ be the minimum number of cycles possible in a $k$-connected graph with cycle rank $r$. We show $f(1,r)=r$, $f(2,r)=(\genfrac{}{}{0ex}{}{r+1}{2})$, $f(3,r)=r^2–r+1$ and characterize the extremal graphs. Bounds are obtained for $f(k,r)$, $k\ge 4$; the upper bound is polynomial in $r$.