The subdivision graph of a graceful tree is a graceful tree (Q1381864): Difference between revisions

A graph \(G= (V,E)\) is graceful, if there is a numbering \(f\) of the vertices from \(1\) to \(| V|\), such that all values \(| f(v)- f(w)|\) are distinct for all edges \(\{v,w\}\in E\). The subdivision graph of a graph is obtained by adding a vertex on the middle of each edge. It is shown that the subdivision graph of a graceful tree is also graceful. The same result holds if exactly \(n\) vertices are inserted on each edge of a graceful tree. The result does not generalize to arbitrary graphs.