Embedding a Graph in a Harmonious Graph or a Graceful Graph

Abstract

Special names are given to graphs that admit vertex- or edge labelings which satisfy some nice properties [I]. For instance, we have the so-called permutation graphs, full graphs, Fibonacci graphs, geometric graphs, magic graphs, graceful graphs, harmonious graphs, tordial graphs and strongly c-elegant graphs. A class of graphs called felicitous graphs generalizes both the harmonious graphs and the strongly c-elegant graphs. Lee,· Schmeichel and Shee [2] gave several examples of felicitous graphs as well as examples of nonfelicitous graphs. They proved that every graph is a subgraph of a harmonious graph. Since every harmonious graph is felicitous, it follows then that every graph is a subgraph of a felicitous graph. We shall also prqve t~at every graph is a subgraph ora graceful graph.

Definations

By a graph G we meari a pair G = (V(G),E(G)), where V(G) is a nonempty finite set of elements called vertices-and E( G) is a set of un9rdered pairs xy called edges, where X and y are • distinct vertices in V"( G)."'Let G be a graph with n1 edges. A harmonious labeling of G is· a
one-to-one ~apping cp : i·r(G) { 0, I, 2, ... , , m -1} such ftiat th_e . - . induced mapping <p : E( G) {0, 1, 2, ... , m - 1 } defined by <p ( e) =cp(x) + <p(y) (mod m) for all e = xy E E(G) is bijective._ A graph is said to be harmonious if it admits a harmonious labeling. Let G be a graph with m edges. A felicitous labeling [3] of G 1s a one-to-one mapping cp : i'(G) { 0, 1, 2, ... , m} such that the induced mapping cp* : £((,) { 0, 1,· 2, ... , m-1} defined by cp*(e) = cp(x) + cp(y) (mod m) for all e = xy E f;(G) is bijective. A graph is said to be felicitous if it admits a felicitous_ labeling. Clearly, every harmonious graph is a felicitous graph.