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.