# Embedding of a Signed Graph with Property $$P$$ in a Graceful Signed Graph with Property $$P$$

## Authors

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

### Synopsis

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$$.

Published
October 10, 2022