Bounding Functions and Rigid Graphs
Michael O. Albertson, Ruth Haas · SIAM Journal on Discrete Mathematics · 1996
A function fbounds graphs from above if there exists an infinite family of graphs $\mathcal{G}$, such that if $G \in \mathcal{G}$ then $f(| V_G |) = | E_G |$ and for all nonempty subgraphs H of G we have that $f(| V_H |) \geq | E_H |$. This paper considers the question: Which functions bound graphs?