Graceful graph

Graceful graph --- грациозный граф.

A graph [math]\displaystyle{ G = (V,E) }[/math] is said to be a graceful graph if there is an injection [math]\displaystyle{ f }[/math] (labelling)

[math]\displaystyle{ f: \; V(G) \rightarrow \{0,1, \ldots, q\} }[/math]

such that the induced function

[math]\displaystyle{ f^{\ast}: \; E(G) \rightarrow \{1,2, \ldots, q\} }[/math]

defined by

[math]\displaystyle{ f^{\ast}(xy) = |f(x) - f(y)| \mbox{ (for all }xy \in E(G)) }[/math]

is an injection.

The images of [math]\displaystyle{ f }[/math] and [math]\displaystyle{ f^{\ast} }[/math] are called respectively vertex and edge labels.

Graceful labellings were first considered by Rosa in 1966.