Minimal \(k\)-extensions of precomplete graphs (Q2386968)

A graph is precomplete if at least one of its vertices is connected to all its other vertices. A graph \(H\) is a \(k\)-extension of a graph \(G\) if \(G\) can be imbedded in any subgraph of \(H\) obtained by removing \(k\) vertices of \(H\) and their incident edges. The trivial \(k\)-extension of \(G\) is obtained from \(G\) by adding \(k\) extra vertices to \(G\) and connecting each of them to every vertex of \(G\) and to each other. \(H\) is a minimal \(k\)-extension of \(G\) if \(H\) has the minimum number of edges of any \(k\)-extension of \(G\) with exactly \(k\) more vertices than \(G\). This article characterizes, as a function of the parity of \(n\) and \(k\), the minimal \(k\)-extensions of any precomplete \(n\)-vertex graph and shows which of them are trivial.