Let $$G=V,E$$ be a p,i¾źq-graph without isolated vertices. The gracefulness gracG of G is the smallest positive integer k for which there exists an injective function $$f:V\rightarrow \{0,1,2,\dots , k\}$$ such that the edge induced function $$g_f:E\rightarrow \{1,2,\dots , k\}$$ defined by $$g_fuv=|fu-fv|$$, $$\forall uv \in E$$ is also injective. Let $$cf=\max \{i: 1,2,\dots , i$$ are edge labels$$\}$$ and let $$mG=\max _f \{cf\}$$ where the maximum is taken over all injective functions [InlineEquation not available: see fulltext.] such that $$g_f$$ is also injective. This new measure mG is called m-gracefulness of G and it determines how close G is to being graceful. In this paper, we prove that there are infinitely many nongraceful graphs with m-gracefulness $$q-1$$, we give necessary conditions for a p,i¾źq-eulerian graph and the complete graph $$K_p$$ to have m-gracefulness $$q-1$$ and $$q-2$$. Using this, we prove that $$K_5$$ is the only complete graph to have m-gracefulness $$q-1$$. We also give an upper bound for the highest possible vertex label of $$K_p$$ if $$mK_p=q-2$$.
['Jessica Pereira', 'Tarkeshwar Singh', 'S. Arumugam']
m-Gracefulness of Graphs