Graceful labelings of nearly complete graphs (Q1601392)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graceful labelings of nearly complete graphs |
scientific article |
Statements
Graceful labelings of nearly complete graphs (English)
0 references
3 September 2002
0 references
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.
0 references
graceful graphs
0 references
graph labelling
0 references
complete multipartite graphs
0 references