Some disgraceful graphs
M. A. Seoud, Robin J. Wilson · International Journal of Mathematical Education in Science and Technology · 1993
A graph with |E| edges is graceful if its edges can be labelled 1,2,..., |E| (used once each) and its vertices can be labelled with distinct numbers from 0 to |E| in such a way that each edge‐label is the difference of the incident vertex‐labels; a graph which is not graceful is called disgraceful. Graceful graphs arise in such applications as coding theory and communication networks. In this paper, we survey the current knowledge about which classes of graphs are graceful, and we present some new examples of disgraceful graphs. The latter include the graphs K4(K3 and K4(K3(K3 and certain graphs of the forms Pn(K3 and Pn(K3(K3. Some generalizations are also considered.