A New Measure for Gracefulness of Graphs

Let G=(V,E) be a (p,q)-graph without isolated vertices. The gracefulness grac(G) of G is the smallest positive integer k for which there exists an injective function f:V→{0,1,2,…,k} such that the edge induced function gf:E→{1,2,…,k} defined by gf(uv)=|f(u)−f(v)| is also injective. Let and let m(G)=maxf⁡{c(f)} where the maximum is taken over all injective functions f:V→N∪{0} such that gf is also injective. This new measure m(G) determines how close G is to being graceful. We determine m(G) for a fe families of nongraceful graphs.