Embedding of a Signed Graph with Property \(P\) in a Graceful Signed Graph with Property \(P\)


Jessica Pereira
School of Physical and Applied Sciences, Goa University, Goa-403206, India
Tarkeshwar Singh
Department of Mathematics, Birla Institute of Technology and Science, Pilani, Goa Campus
S. Arumugam
National Centre for Advanced Research in Discrete Mathematics, Kalasalingam University, Anand Nagar, Krishnankoil-626 126, Tamil Nadu, India


Let \(S = (V, E, s)\) be a signed graph with \(|V|=p, |E|=q\) and let \(s: E \rightarrow\{+, -\}\) be a function which assigns a sign + or - to each edge. For any injection \(f: V \rightarrow\{0, 1, …, q\}\), the induced edge labelling gf is defined by \(g_f(uv)=s(uv)|f(u)-f(v)|\). The function f is said to be a graceful labelling of S, if \(g_f(E^+) = \{1, 2, …, |E^+|\}\) and \(g_f(E^-) = \{-1, -2, …, -|E^-|\}\) where E+ and E- denote the set of all positive and negative edges of S respectively. A signed graph that admits graceful labelling is called a graceful signed graph. In this paper, we prove that a signed graph S having property P can be embedded in a graceful signed graph S' having property P when P denotes the property being: triangle-free, planar, Eulerian, or Hamiltonian. We have also proved that if S is a connected graph and S1, S2, … Sk is its decomposition into edge-induced subgraphs with \(f: V \rightarrow N \cup \{0\} \) an injection having maximum vertex label MS(f), such that the edge-induced function gf assigns distinct labels to edges of \(S_i, 1 \leq i \leq k\). Then S can be embedded as an induced subgraph of k-hypergraceful eulerian graph S' with k‑hypergraceful labelling h such that \(M_{S'(h)} \leq 2^{k+1}(M_{S(f)}+4)-7\).

October 10, 2022