m-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 g_f : E → {1,2,…, k} defined by g_f (uv) = |f(u) -f{v)|, (A)uv ∈ E is also injective. Let c(f) = max{i : 1,2,… ,i are edge labels} and let m(G) = max_f{c(f)} where the maximum is taken over all injective functions f : V → IN ∪ {0} such that g_f is also injective. This new measure m(G) 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,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 m(K_p) = q - 2.