Embeddings in Eulerian graceful graphs.
Siddani Bhaskara Rao, Uma kant Sahoo · Australas. J Comb. · 2015
Let G(V,E) be a graph of order n and size m. A graceful labeling of G is an injection f : V (G) → {0, 1, 2, ...,m} such that, when each edge uv is assigned the label f(uv) = |f(u)− f(v)|, the resultant edge labels are distinct. We focus on general results in graceful labelings, and provide an affirmative answer to the following open problem: Can every connected graph be embedded as an induced subgraph in an Eulerian graceful graph? As a result we infer that the problems on deciding whether the chromatic number is less than or equal to an integer k, for k ≥ 3, and deciding whether the clique number is greater than or equal to an integer k, for k ≥ 3, are NP-Complete even for Eulerian graceful graphs.