The measurements of closeness to graceful graphs.
Rikio Ichishima, Francesc Antoni Muntaner-Batle, Akito Oshima · 2015
The beta-number, β (G), of a graph G is defined to be either the smallest positive integer n for which there exists an injective function f : V (G) → {0, 1, . . . , n} such that each uv ∈ E (G) is labeled |f (u)− f (v)| and the resulting set of edge labels is {c, c+ 1, . . . , c+ |E (G)| − 1} for some positive integer c, or +∞ if there exists no such integer n. If c = 1, the resulting beta-number is called the strong beta-number of G and denoted by βs (G). In this paper, some necessary conditions for a graph to have finite (strong) beta-number are presented, which lead us to sufficient conditions for a graph to have infinite (strong) beta-number. By means of these, the formulas for the (strong) beta-number of certain graphs are determined. Moreover, nontrivial trees and forests are shown to have finite strong beta-number. Finally, three open problems are proposed.