A graph on \(n\) vertices having no vertex of degree greater than \(f\), \(2 \leq f \leq n – 2\), is called an \(f\)-graph of order \(n\). For a given \(f\), the vertices of degree less than \(f\) are called orexic. An \(f\)-graph to which no edge can be added without violating the \(f\)-degree restriction is called an edge maximal \(f\)-graph (EM \(f\)-graph). An upper bound, as a function of \(n\) and \(f\), for the number of orexic vertices in an EM \(f\)-graph and the structure of the subgraph induced by its orexic vertices is given. For any \(n\) and \(f\), the maximum size, minimum size, and realizations of extremal size EM \(f\)-graphs having \(m\) orexic vertices and order \(n\) are obtained. This is also done for any given \(n\) and \(f\) independent of \(m\). The number of size classes of EM \(f\)-graphs of order \(n\) and fixed \(m\) is determined. From this, the maximum number of size classes over all \(m\) follows. These results are related to the study of \((f + 1)\)-star-saturated graphs.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.