The Maximum Number of One-Edge Extensions For Graphs with Bounded Degree

Abstract

The maximum number of non-isomorphic one-edge extensions \(M(t, n, f)\) of a graph of size \(t\), order \(n\), and vertex degree bounded by \(f\) for \(3 \leq f \leq n-2\) is considered. An upper bound for \(M(t, n, f)\) is obtained, and for the case \(f = n-2\), the exact value is given. Tables are provided for all values of \(M(t, n, f)\) for up to \(n = 12\), \(\left\lfloor \frac{f-1}{2} \right\rfloor < t \leq \left\lfloor \frac{nf}{2} \right\rfloor\), and \(3 \leq f \leq n-2\). Additionally, the relation of these results to the transition digraph for the Random \(f\)-Graph Process, a Markov process concerning graphs with vertex degree bounded by \(f\), is noted.