Graceful labelings of nearly complete graphs (Q1601392)

A graph with \(q\) edges is graceful, if we can assign to each vertex an integer in \(\{0, 1, \ldots, q\}\), such that all edges have a different value of the absolute difference of the labels of its endpoints. This paper investigates which graphs that are `nearly complete', or a complete multipartite graph, are graceful. In particular, it is shown that \(K_n-e\) is graceful only if \(n\leq 5\), and \(K_n-2e\) and \(K_n-3e\) are graceful only if \(n\leq 6\). The graceful graphs of the form \(K_n - K_{1,a}\) (\(a\leq n-2\)) or \(K_n - M\) (\(M\) a matching) are also determined. It is shown that \(K_{a,b}\), \(K_{1,a,b}\), \(K_{2,a,b}\), and \(K_{1,1,a,b}\) are graceful. A computer experiment gives rise to the conjecture that these are the only gracefull complete multipartite graphs.