Graceful Labelings of Nearly Complete Graphs

It is well known that the complete graph K_n is graceful only if n ≤ 4. We prove that K_n — e is graceful only if n ≤ 5 and that any K_n—2e and any K_n — 3e is graceful only if n ≤ 6. Moreover we determine all graceful graphs K_n — G, if G is a star K_1,a with a ≤ n - 2, and if G is a matching M_a with 2a ≤ n. Furthermore we give graceful labelings for the complete multipartite graphs K_1,a,b, K_2,a,b K_1,1,a,b and we conjecture that these together with K_a,b are the only complete multipartite graphs which are graceful.