We prove the following necessary conditions for signed graphs on complete graphs to admit additive graceful labelings, thus considerably narrowing down the search for such labelings. If a signed graph on a complete graph \(K_p, ~p\not = 4\), with \(n\) negative and \(m\) positive edges, admits an additively graceful labeling, then (1) \(p\), \(p-2\) or \(p-4\) must be a perfect square, (2) If \(p\) is a perfect square then, both \(m\) and \(n\) are even, (3) If \(p-4\) is a perfect square then, both \(m\) and \(n\) are odd, (4) If \(p-2\) is a perfect square then, \(m\) and \(n\) have opposite parity and (5) The number of odd and even labeled vertices in \(S\) are \(\frac{p+\sqrt{p-i}}{2}\) and \(\frac{p-\sqrt{p-i}}{2}\) according as \(p-i\) is a perfect square, \(i=0,2\) or \(4\). We also provide an example to show that, if a signed graph \(S\) with no negative edges is additively graceful then, \(S\) as a graph need not be graceful. Interestingly, this example also settles 3 more open problems concerning gracefulness and edge consecutive gracefulness (ecg), thereby demonstrating that ecg or \(m\)-gracefulness is not a reliable measure of gracefulness.
Throughout our discussions, a graph \(G\) will refer to a finite, nonempty set of objects known as vertices, along with a collection of unordered pairs of distinct vertices called edges. The sets of vertices and edges are represented by \(V(G)\) and \(E(G)\), respectively, whereas their cardinality is denoted by \(p\) and \(q\), respectively, in which case \(G\) is called a \((p,q)\) graph. All basic terminology related to Graph Theory which we will use can be found in Chartrand and Lesniak [1].
An injective map from \(V(G)\) to \(\mathbb{Z}\) is called a vertex labeling of \(G\) while an edge labeling is an injective map from \(E(G)\) to \(\mathbb{Z}\). Although vertices and edges may be labeled independently, we will be interested in associating with a vertex labeling an edge labeling as follows. Given a vertex labeling \(f : V(G)\rightarrow \mathbb{Z}\), we obtain the induced edge labeling \(f^* : E(G)\rightarrow \mathbb{N}\) by setting \(f^*(uv)\) to be \(|f(u)-f(v)|\). The edge labels thus obtained are called induced edge labels.
Observation 1.1.[2] If \(f\) is a vertex labeling in graph \(G\), then for any integer \(k\), both the vertex labelings \(g= f +k\) as well as \(g=-f+k\) satisfy \(f^* = g^*\).
We denote \(\max_{v \in V(G)} f(v)\) by \(M_f(G)\). Then, \(M_f(G)-f\) is called the complementary labeling of \(f\).
Definition 1.2. Let \(G\) be a \((p,q)\) graph. A graceful labeling of \(G\) is an injection \(f:V(G)\rightarrow \{0,1,\dots, q\}\) such that when each edge \(uv\) is assigned the label \(f^*(uv) = |f(u)-f(v)|\), the resulting edge labels are all distinct. A graph which admits such a labeling is called a graceful graph.
Rosa [10] called such a labeling as a \(\beta\)-valuation and Golomb [4] subsequently called it graceful labeling.
Observation 1.3. In any graceful labeling of a \((p,q)\) graph \(G\) with \(q\geq1\), an edge labeled \(q\) always exists and is incident with vertices labeled \(0\) and \(q\).
Observation 1.4. The complementary labeling of a graceful labeling is also a graceful labeling.
Hegde [6] introduced the concept of additively graceful graphs and gave a characterization for additively graceful complete graphs. The definition of additively graceful graphs in Hegde [6] requires the \(p\) vertices of a \((p,q)\) graph to be labeled using labels 0, 1, \(\dots, \lceil{\frac{q+1}{2}}\rceil\). Hence, when \(q\) is odd, we would need \(\frac{q+1}{2}+1 \geq p\). This gives the bound \(q \geq 2p-3\). Whereas, when \(q\) is even, we would need \(\frac{q+2}{2}+1 \geq p\), thus resulting in the bound \(q \geq 2p-4\).
Definition 1.6. [6] Let \(G\) be a \((p,q)\) graph satisfying \(q \geq 2p-4\). An additively graceful labeling of \(G\) is an injection \(f:V(G)\rightarrow \{0,1,\dots, \lceil{\frac{q+1}{2}}\rceil\}\), such that when each edge \(uv\) is assigned the label \(f^*(uv) = f(u)+f(v)\), we have \(f^*(E(G))=\{1,2,\dots,q\}\). A graph which admits such a labeling is called an additively graceful graph.
Theorem 1.7. [6] The graph \(K_{p}\) is additively graceful if and only if \(p \leq 4\).
Theorem 1.8. [6] An additively graceful graph is either \(K_2\) or \(K_{1,2}\) or has a triangle.
Building on the work in [6], Pereira et al. [9] generalized the concept of additively graceful graphs by defining additively graceful signed graphs. A signed graph \(S\), is a \((p,q)\) graph in which certain \(m\) edges are specified as positive and the remaining \(n\) edges are specified as negative. We call \(S\) a \((p,m,n)\) signed graph and denote the set of positive and negative edges by \(E^+\) and \(E^-\), respectively. \(S\) shall be called all positive (or all negative) if all its edges are positive (or negative). In diagrams of signed graphs, we will use a solid line to represent a positive edge, while a dashed line shall represent a negative edge (see Figures 1 and 2).
Definition 1.9. [9] Let \(S=(V,E)\) be a \((p,m,n)\) signed graph. Let \(f:V \rightarrow \{0,1,\dots, m+\lceil\frac{(n+1)}{2}\rceil\}\) be an injective mapping and let the induced edge function be defined as \(f^*(uv)=f(u)+f(v), ~ \forall ~ uv \in E^-\) and \(f^*(uv)=|f(u)-f(v)|,~\forall~ uv \in E^+\). If \(\{f^*(uv):uv \in E^-\}=\{1, 2, …, n\}\) and \(\{f^*(uv):uv \in E^+\}=\{1, 2, …, m\}\), then \(f\) is called an additively graceful labeling of \(S\). A signed graph which admits such a labeling is called an additively graceful signed graph.
The following three theorems are obtained in [9].
Theorem 1.10. [9] For \(m=0\), the signed graph \(S\) on \(K_{p}\) is an additively graceful signed graph if and only if \(p \leq 4\).
Theorem 1.11. [9] Let \(p \geq 5\) be a positive integer such that none of \(p\), \(p-2\), \(p-4\) is a perfect square. Then, no signed graph on \(K_p\) is additively graceful.
Theorem 1.12. [9] If a \((p,m,n)\) signed graph on \(K_p\), where \(p = x^2\), \(x^2 + 2\), \(x^2 + 4\); \(x\) odd, is additively graceful, then \(n\) is
(a) even for \(p=x^2\).
(b) even or odd for \(p=x^2+2\).
(c) odd for \(p=x^2+4\).
The following complete characterizations for additively graceful signed paths and signed cycles have been obtained in [2].
Theorem 1.13. [2] A signed path \(S\) with \(n\) negative edges is additively graceful if and only if \(n \leq 2\) and \(S\) has at most one negative section, except that the four signed paths in Figure 1 are not additively graceful.
Theorem 1.14. [2] A signed cycle \(S\) with \(m\) positive and \(n\) negative edges, is additively graceful if and only if one among the following 4 conditions is satisfied,
(a) \(n=0\) and \(m\equiv 0\) or \(3 \pmod 4\).
(b) \(n=1\) and \(m\equiv 1\) or \(2 \pmod 4\).
(c) \(n=2\), \(m\equiv 1\) or \(2 \pmod 4\) and \(S\) contains a single negative section.
(d) \(S\) is the all negative signed cycle on \(C_3\).
Motivated by the existance of such elegant characterizations we have attempted to characterize additively graceful signed graphs on complete graphs. Although such a characterization has not been found, we have obtained some necessary conditions, which we present in Section 2 and which considerably narrow down the search for such labelings. We provide an alternate proof to Theorem 1.11 and generalize Theorem 1.12 to include the case when \(x\) is even, while additionally providing the parity of \(m\) and the number of odd and even labeled vertices. We also establish a few more results that further the understanding of additively graceful labelings of signed graphs on \(K_p\).
Further this investigation into additively graceful labelings of signed graphs has unexpectedly led to the resolution of three open questions on the gracefulness of graphs, thereby reinforcing the notion that the study of variations of conventional labelings is a meaningful pursuit — for while one goal may elude us, another often emerges in its place.
In [5], Graham and Sloane established an unpublished result of Erdős which states that almost all graphs are not graceful. Many concepts have since been proposed to quantify how close a graph is to being graceful.
Definition 1.15. [1] The gracefulness grac\((G)\) of a graph \(G\) with \(V(G) = \{v_1,v_2,\dots,v_p\}\) and without isolated vertices is the smallest positive integer \(k\) for which it is possible to label the vertices of \(G\) with distinct elements from the set \(\{0, 1,\dots,k\}\) in such a way that distinct edges receive distinct labels. Such vertex labelings always exist, one of which is to label \(v_i\) by \(2^{i-1}\).
Definition 1.16. [8] Let \(f: V(G) \rightarrow \mathbb{N} \cup \{0\}\) be a vertex labeling such that the edge labeling \(f^*\) is injective where \(f^*(uv)=|f(u)-f(v)|\). Let \(r(f)\) be the largest integer such that \(\{1,2,…, r(f)\} \subset f^*(E)\). Then, m-gracefulness or edge consecutive gracefulness(ecg) of \(G\) is given by \(m(G)=ecg(G):= max_{f} \{ r(f)\}\).
\(G\) is graceful if and only if grac\((G) = q\), but certain questions remain unanswered. The following problem is posed in [1] and remains open.
Problem 1.17. [1] By definition, a vertex labeling \(f\) of \(G\) which realizes grac\((G)\) must have \(f(v)=\) grac\((G)\) for some vertex \(v\), but it is not known whether an edge of \(G\) must then be labeled grac\((G)\).
Problem 1.18. If \(G\) is graceful, then \(ecg(G) = q\), but it is not known if the converse is true.
In [7] and [8], Pereira et al. posed a problem similar to these, which still remains open. They proved that grac\((K_p)-q= q-ecg(K_p)\) for \(p \leq 6\) and went on to show that there exists infinitely many non-graceful graphs satisfying \(grac(G)-q = q-ecg(G)\). Hence, they asked the following.
Problem 1.19. [8] Is it true that \(grac(G)-q = q-ecg(G)\) for all graphs?
Remark 1.20. If Problem 1.18 is proved in the affirmative, then it would establish that \(m(G)\) is sensitive enough to detect non-gracefulness. This is essential to justify that “\(m(G)\) determines how close \(G\) is to being graceful”, an assertion which has been made in Gallian [3]. Further, if Problem 1.19 is proved in the affirmative, then it would establish that ecg(G) and grac(G) measure non-gracefulness in equal measure.
We have settled Problems 1.17, 1.18 and 1.19 in Section 3, as well as the following question.
Problem 1.21. If an all positive signed graph is additively graceful, then is it graceful as a graph?
In [9], it is stated that additively graceful signed graphs are a generalization of graceful graphs, thus providing an affirmative answer to Problem 1.21. In Section 3, we show that this is an oversight and there indeed exists non-graceful graphs which are additively graceful when considered as all positive signed graphs.
The following is a basic observation which follows directly from the definitions of a graceful graph and an additively graceful signed graph.
Observation 2.1. [2] If a graph \(G\) is graceful, then as a signed graph with \(n=0\), it is an additively graceful signed graph.
One should note that, it is not directly evident if the converse of Observation 2.1 holds. This is because the definition of additively graceful signed graph with \(n=0\) allows \(m+1\) to potentially be a vertex label. We show in Theorem 3.2, (see Figure 3(a)), that indeed the converse of Observation 2.1 does not hold.
Throughout this section, we investigate additively graceful labelings of signed graphs on the complete graph \(K_{p}\). Hence \(q=\frac{p(p-1)}{2}\). The case \(m=0\) has been characterized in Theorem 1.10. We now settle the case \(n=0\). Since the converse of Observation 2.1 does not hold, hence, Theorem 2.2 is not an obvious consequence of Theorem 1.5.
Theorem 2.2. The all positive signed graph on \(K_{p}\) is additively graceful if and only if \(p \leq 4\)
Proof. Let \(S\) be the all positive signed graph on \(K_{p}\). Suppose \(p > 4\), then by Theorem 1.5, we know that \(K_p\) is not graceful. Hence, \(S\) does not admit an additively graceful labeling with vertex labels restricted to the set \(\{ 0,1,…, q\}\). Therefore, if \(S\) is additively graceful, then it must admit an additively graceful labeling \(f:V(S)\rightarrow \{0,1,\dots,q+1\}\) such that \(q+1 \in f(V(S))\). Now, if \(0 \in f(V(S))\), then \(q+1 \in f^*(E(S))\), resulting in a contradiction. Thus, no vertex is assigned the label \(0\) by \(f\). It is hence possible to define \(g:V(S)\rightarrow \{0,1,\dots,q\}\) by, \[g(v)=f(v)-1.\]
Using Observation 1.1, we can conclude that, \(g\) is a graceful labeling of \(K_p\), thus giving a contradiction to Theorem 1.5.
Conversely, if \(p \leq 4\), then by Theorem 1.5, \(S\) is graceful. By Observation 2.1, it follows that \(S\) is an additively graceful signed graph. ◻
Theorem 2.3 gives an alternate proof to Theorem 1.11, provides a generalization of Theorem 1.12 and gives some additional information about the vertex labels.
Theorem 2.3. Let \(p\not=4\) be a positive integer. If the signed graph \(S\) on \(K_{p}\) admits an additively graceful labeling \(f\), then
(a) \(p\), \(p-2\) or \(p-4\) must be a perfect square.
(b) If \(p\) is a perfect square then, both \(m\) and \(n\) are even.
(c) If \(p-4\) is a perfect square then, both \(m\) and \(n\) are odd.
(d) If \(p-2\) is a perfect square then, \(m\) and \(n\) have opposite parity.
(e) The number of odd and even labeled vertices in \(S\) are \(\frac{p+\sqrt{p-i}}{2}\) and \(\frac{p-\sqrt{p-i}}{2}\) according as \(p-i\) is a perfect square for \(i=0,2,4\).
Proof. Let \(V_e\) and \(E_e\) be the set of vertices and edges respectively, in \(S\), whose labels are even and let \(V_o\) and \(E_o\) be the set of vertices and edges respectively, in \(S\), whose labels are odd. Suppose \(|V_e|=a\), then \(|V_o|=p-a\), (or vice-versa) and hence, \[\label{eqn1:main result on add grac of complete signed graphs} |E_o|=a(p-a)=ap-a^2. \tag{1}\] \[ \label{eqn2:main result on add grac of complete signed graphs} \text{ If $m$ and $n$ are both even, then $|E_o|=\frac{m}{2}+\frac{n}{2}=\frac{q}{2}$ }.\ \tag{2}\] \[\label{eqn3:main result on add grac of complete signed graphs} \text{ If $m$ and $n$ are both odd, then $|E_o|=\frac{m+1}{2}+\frac{n+1}{2}=\frac{q+2}{2}.$ }\ \tag{3}\] \[\label{eqn4:main result on add grac of complete signed graphs} \text{ If $m$ and $n$ have opposite parity, then $|E_o|=\frac{q+1}{2}.$ } \ \tag{4}\]
Case A. If \(m\) and \(n\) are both even.
From Eq. (1) and Eq. (2) we get, \[ap-a^2=\frac{p(p-1)}{4}.\]
Which simplifies to the quadratic equation \(4a^2-4pa+(p^2-p)=0\).
\[\text{The roots of this quadratic equation are given by }a=\frac{p \pm \sqrt{p}} {2}. \tag{5}\]
Case B. If \(m\) and \(n\) are both odd.
From Eq. (1) and Eq. (3) we get, \[ap-a^2=\frac{p(p-1)+4}{4}.\]
Which simplifies to the quadratic equation \(4a^2-4pa+(p^2-p+4)=0\).
\[\text{The roots of this quadratic equation are given by}a=\frac{p \pm \sqrt{p-4}} {2}. \tag{6}\]
Case C. If \(m\) and \(n\) have opposite parity.
From Eq. (1) and Eq. (4) we get, \[ap-a^2=\frac{p(p-1)+2}{4}.\]
Which simplifies to the quadratic equation \(4a^2-4pa+(p^2-p+2)=0\).
\[\text{The roots of this quadratic equation are given by}, a=\frac{p \pm \sqrt{p-2}} {2}. \tag{7}\]
We require \(a\) to be an integer and hence, either \(p\), \(p-2\) or \(p-4\) must be a perfect square, thus proving (1).
Since \(p\not = 4\), hence for a given value of \(p\), only one among \(p\), \(p-2\) or \(p-4\) can possibly be a perfect square. Therefore, conclusions (2), (3) and (4) immediately follow from Cases (A), (B) and (C).
Finally, suppose \(a\) is fixed as one of the roots in Eq. (5), Eq. (6) or Eq. (7), according as \(p\), \(p-4\) or \(p-2\), respectively, is a perfect square. It can be verified that in all 3 cases, the other root is \(p-a\). It follows that the number of odd and even labeled vertices in \(S\) are \(\frac{p+\sqrt{p-i}}{2}\) and \(\frac{p-\sqrt{p-i}}{2}\) (or vice-versa), according as \(p-i\) is a perfect square for \(i=0,2,4\). ◻
Observe that, \(p=4\) is the only case in which \(p\) as well as \(p-4\) are perfect squares. Hence, if we follow the steps in the proof of Theorem 2.3, we see that, in an additively graceful labeling of \(K_4\), the number of odd and even vertices will both be \(2\) or will be \(3\) and \(1\). Accordingly, \(m\) and \(n\) are either both odd or both even, respectively (see Figure 2).
It is also worth noting that any perfect square is of the form \(4t\) or \(4t+1\) for some \(t \in \mathbb{N}\). Hence, if \(k\) or \(k-4\) is a perfect square, then \(q=k(k-1)/2\) is even. In this case, it is always possible to partition \(q\) as even+even or odd+odd. Whereas, if \(k-2\) is a perfect square, then \(q=k(k-1)/2\) is odd and can always be partitioned as even+odd.
The highest vertex label permitted in an additively graceful labeling of a signed graph on \(K_{p}\) is \(m+ \lceil \frac{n+1}{2} \rceil\). Theorem 2.5 provides an alternate bound which is considerably sharper when \(m\) and \(n\) are close to \(\frac{q}{2}\).
Observation 2.4. [2] If an additively graceful signed graph \(S\) has one or more negative edges then the negative edges, labeled \(1\) and \(2\) must be incident with the vertex labeled \(0\).
Theorem 2.5. If the signed graph \(S\) on \(K_{p}\), \(p \geq 5\) is assigned an additively graceful labeling \(f\), then \(f(v) \leq max \{n,m \}\) for every \(v \in V(S)\).
Proof. Since \(p \geq 5\), by Theorem 2.2, we must have \(n \geq 1\). Hence, by Observation 2.4, there exists a vertex \(u\) for which \(f(u)=0\). For some \(v \in V(S)\), if \(f(v) > max \{n,m \}\), then the edge \(uv\) (irrespective of being positive or negative) will be labeled \(f(v)\), which is a contradiction. ◻
The graph in Figure 2(f), shows that Theorem 2.5 may not hold for \(p<5\). Theorem 2.3 and Theorem 2.5 are extremely useful in narrowing down the possibilities, while constructing additively graceful labelings of signed graphs on complete graphs. Using a computer program and incorporating these two theorems, we have been able to obtain all the additively graceful labelings of signed graphs on \(K_p\) for \(p\leq 10\). Table 1 lists the number of such labelings obtained. The entries in the \(p^{th}\) column of the table give the number of distinct additively graceful labelings possible for a signed graph on \(K_p\), for various values of \(n\) (number of negative edges). For example, there are 10 distinct additively graceful labelings possible for signed graphs on \(K_6\) with 9 negative edges, but only 6 such labelings for \(K_6\) with 8 negative edges. Corresponding to \(p=1,2,\dots,7\), additively graceful labelings exists only for \(n\) lying between 0 and 12 while only values of \(n\) lying between 13 and 24 yield additively graceful labelings for \(p=8\) and 9. Two such labelings for signed graphs on \(K_8\) and \(K_9\) are given in Figure 4. Table 1 shows the number of additively graceful labelings of signed graphs on \(K_p\), for \(p \leq 10\), corresponding to various values of \(n\) (the number of negative edges).
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| 0 | 2 | 2 | 4 | 4 | – | – | – |
| 1 | – | 1 | 1 | 1 | 1 | – | – |
| 2 | – | – | 1 | 1 | – | – | – |
| 3 | – | – | 1 | 1 | 1 | 1 | – |
| 4 | – | – | – | – | – | – | – |
| 5 | – | – | – | 1 | 2 | – | – |
| 6 | – | – | – | 1 | – | 1 | – |
| 7 | – | – | – | – | 4 | 4 | – |
| 8 | – | – | – | – | – | 6 | – |
| 9 | – | – | – | – | 1 | 10 | – |
| 10 | – | – | – | – | – | 9 | – |
| 11 | – | – | – | – | – | 3 | – |
| 12 | – | – | – | – | – | 2 | – |
Although a graceful graph is not required to be connected, non-gracefulness of disconnected graphs is not given much significance in the literature. For example, in [1] it is stated that, “there are precisely 3 graphs of order 5 which are not graceful”, namely \(C_5\), \(K_5\) and \(K_1+(K_2 \cup K_2)\), when in fact \(\overline{K_5}\) and the graphs of order 5 in Figure 5 are also not graceful, but are ignored on account of being disconnected. The acyclic graphs in Figure 5 are not graceful because \(p>q+1\). We leave it to the reader to verify that the remaining three graphs are also not graceful. Any of the graphs in Figure 5 can be used to provide a negative answer to Problems 1.17, 1.18, 1.19 and 1.21, but these graphs are not connected.
In this section, we provide an example of a connected graph which is not graceful but which is additively graceful when considered as an all positive signed graph. We then show that this example settles Problems 1.17, 1.18 and 1.19.
We say that two graceful labelings of a graph \(G\) are equivalent upto complementary labeling if one is the complementary labeling of the other.
Lemma 3.1. Let \(G=G_1+G_2\) where \(G_1= \overline{K_2}\) and \(G_2= K_2 \cup K_2\). If \(G\) is graceful and if \(L_{i},~ i=1,2\) denotes the set of vertex labels of \(G_{i}\) in any graceful labeling of \(G\), then the labels in \(L_1\) have opposite parity and exactly one label in \(L_2\) is either even or odd. Further the graceful labelings of \(G\), equivalent upto complementary labeling, can be categorized into 3 mutually exclusive and exhaustive types as follows (See Figures 3 (b), (c) and (d)).
(a) \(0 \in L_1\), \(10 \in L_2\) and all other vertex labels are odd.
(b) \(0 \in L_1\), \(10 \in L_2\) and exactly one label in \(L_2\) is odd.
(c) \(1 \in L_1\), \(G_2\) contains an edge incident with vertex labels \(0\) and \(10\) and exactly one label in \(L_2\) is odd.
Proof. Suppose \(G\) admits a graceful labeling. It follows that, out of the \(10\) edges in \(G\), exactly 5 edges are even and exactly 5 are odd.
Now, suppose both the labels in \(L_1\) are even. If the number of odd labels in \(L_2\) is less than \(2\), then \(G\) can have at most \(3\) odd edges. On the other hand, if the number of odd labels in \(L_2\) is greater than \(2\), then \(G\) will have at least \(7\) odd edges. Hence, exactly 2 labels in \(L_2\) are odd. This results in 4 odd edges joining vertices in \(G_1\) with vertices in \(G_2\). To obtain the required fifth odd edge label, we must have vertices of opposite parity connected by an edge in \(G_2\). But this would force the other edge in \(G_2\), to also be odd, thus resulting in 6 odd edges. Similarly, one can prove that both the labels in \(L_1\) cannot be odd. Hence, the 2 vertices in \(L_1\) must have opposite parity in a graceful labeling of \(G\).
Further, it can easily be verified that, to obtain the required 5 odd and 5 even edge labels in a graceful labeling of \(G\), precisely one label in \(L_2\) must either be even or odd.
Case A. Exactly one label in \(L_2\) is even:
By Observation 1.3, the two even labeled vertices in \(G\) must be labeled \(0\) and \(10\). In the complementary labeling these vertex labels get interchanged. Hence without loss of generality we can assume that \(0 \in L_1\) and \(10 \in L_2\). The remaining vertex labels are obviously odd. This gives labelings of Type 1.
Case B. Exactly one label in \(L_2\) is odd:
Observation 1.3 requires that there must exist an edge in \(G\) with its incident vertices labeled \(0\) and \(10\).
First, if this edge joins a vertex in \(G_1\) to a vertex in \(G_2\), then by exactly the same reasoning used in Case A, we can, without loss of generality, assume that \(0 \in L_1\) and \(10 \in L_2\). This gives the labelings of Type 2.
Second, if the edge labeled \(10\) joins vertices within \(L_2\), then the edge label \(9\) can be either obtained as \(|10-1|\) with \(1\) inserted in \(L_1\) or as \(|9-0|\) with \(9\) inserted in \(L_1\). But since we are considering labelings equivalent upto complementary labeling, we see that these 2 cases are actually the same. Hence, without loss of generality, we can assume that \(1 \in L_1\). This gives the labelings of Type 3. With this, we have exhausted all possibilities. ◻
Theorem 3.2. The graph \(\overline{K_2}+(K_2 \cup K_2)\) is not graceful but as an all positive signed graph it is additively graceful.
Proof. Suppose \(G=G_1+G_2\) where \(G_1= \overline{K_2}\) and \(G_2= K_2 \cup K_2\). As an all positive signed graph, \(G\) admits an additively graceful labeling as shown in Figure 3(a). Hence, G is an additively graceful signed graph.
Now, if \(G\) admits a graceful labeling and if \(L_{i},~ i=1,2\) denotes the set of vertex labels of \(G_{i}\), then we consider the 3 cases corresponding to the 3 types of labelings given by Lemma 3.1 ( see Figure 3).
Case 1. \(0 \in L_1\), \(10 \in L_2\) and all other vertex labels are odd.
Here, the edge label \(9\) can be obtained as \(|10-1|\) or as \(|9-0|\). We get 3 sub-cases as follows,
Sub-Case 1.1. The edge label \(9\) is obtained as \(|10-1|\) by inserting \(1\) in \(L_1\).
From the parity of the vertex labels we see that, edge label \(8\) cannot be obtained without creating repeated edge labels (see Figure 6).
Sub-Case 1.2. The edge label \(9\) is obtained as \(|10-1|\) by inserting \(1\) in \(L_2\).
Here also, edge label \(8\) cannot be obtained without repeating edge labels.
Sub-Case 1.3. The edge label \(9\) is obtained as \(|9-0|\) by inserting \(9\) in \(L_2\).
Now, the edge label \(8\) can only be obtained as \(|9-1|\) by inserting \(1\) in \(L_2\) (It is not possible to insert \(1\) in \(L_1\), as this will cause the edge label \(9\) to be repeated). Now, observe that inserting \(5\) in either \(L_1\) or \(L_2\) creates repeated edge labels. Hence, the remaining 2 vertex labels can only be \(3\) and \(7\), but it can easily be verified that this does not give a graceful labeling.
Case 2. \(0 \in L_1\), \(10 \in L_2\) and exactly one label in \(L_2\) is odd.
Edge label \(9\) can be obtained as \(|9-0|\) or \(|10-1|\). We get 3 sub-cases as follows,
Sub-Case 2.1. Consider edge label \(9\) obtained as \(|9-0|\) by taking \(9\) in \(L_2\). Now, edge label \(8\) can be obtained as \(|8-0|\) or \(|10-2|\) but not as \(|9-1|\). Thus, we get 2 further sub-cases as follows
Sub-Case 2.1.1. Here, edge label \(8\) is obtained as \(|8-0|\) by inserting \(8\) in \(L_2\). It follows that the only way to obtain edge label \(7\) (without repeating edge labels), is as \(|10-3|\) by having \(3\) in \(L_1\). The final label in \(L_2\) must be one among the even numbers \(2\), \(4\) or \(6\). It can be verified that in all 3 cases, an edge label is repeated, thus giving a contradiction (see Figure 7).
Sub-Case 2.1.2. Here, edge label \(8\) is obtained as \(|10-2|\) by inserting \(2\) adjacent to \(10\) in \(L_2\). It follows that the only way to obtain edge label \(7\) is as \(|10-3|\) by having \(3\) in \(L_1\). The final label in \(L_2\) must be one among the even numbers \(4\), \(6\) or \(8\). It can be easily verified that in all 3 cases, an edge label is repeated, thus, giving a contradiction.
Sub-Case 2.2. Consider edge label \(9\) obtained as \(|10-1|\) by taking \(1\) as the odd label in \(L_1\). Now, edge label \(8\) can be obtained as \(|8-0|\) or \(|10-2|\) but not as \(|9-1|\). Thus, we get 2 further subcases as follows.
Sub-Case 2.2.1. Here, edge label \(8\) is obtained as \(|8-0|\) by inserting \(8\) in \(L_2\). This also creates edge label \(7\) as \(|8-1|\). Now, the lone odd label in \(L_2\) can either be \(3\) or \(5\), while the final label in \(L_2\) must be from the set \(\{2,4,6\}\). It can easily be verified that in all 6 cases, an edge label is repeated, thus, giving a contradiction.
Sub-Case 2.2.2. Here, edge label \(8\) is obtained as \(|10-2|\) by inserting \(2\) adjacent to \(10\) in \(L_2\). It follows that the only way to obtain edge label \(7\) is as \(|7-0|\) by having \(7\) in \(L_2\). The final label in \(L_2\) must be one among the even numbers \(4\), \(6\) or \(8\). It can be easily verified that in all 3 cases, an edge label is repeated, thus, giving a contradiction (see Figure 8).
Sub-Case 2.3. Consider edge label \(9\) obtained as \(|10-1|\) by taking \(1\) as the odd label in \(L_2\). Now, edge label \(8\) can only be obtained as \(|8-0|\) by inserting \(8\) in \(L_2\). Also, edge label \(7\) can only be obtained as \(|10-3|\) by inserting \(3\) in \(L_1\). The final label in \(L_2\) must be one among the even numbers \(2\), \(4\) or \(6\). It can be easily verified that in all 3 cases, an edge label is repeated, thus, giving a contradiction.
Case 3. \(1 \in L_1\), \(G_2\) contains an edge incident with vertex labels \(0\) and \(10\) and exactly one label in \(L_2\) is odd.
Observe that the only way to obtain edge label \(7\), without creating repeated edge labels, is as \(|8-1|\), by inserting \(8\) in \(L_2\). This leaves only one possibility to obtain edge label \(8\), i.e., by taking \(2\) as the even label in \(L_1\) and thus, obtaining the edge label \(|10-2|\). The final label in \(L_2\) must be one among the odd numbers \(3\), \(5\), \(7\) or \(9\). It can be easily verified that in all 4 cases, an edge label is repeated, thus, giving a contradiction.
We hence conclude that, \(G\) is not graceful. ◻
Corollary 3.3. The gracefulness of the graph \(\overline{K_2} + (K_2 \cup K_2)\) is \(11\).
Proof. By Theorem 3.2, \(G\) is not graceful but by the labeling presented in Figure 3(a), there exists a labeling \(f:V(G) \rightarrow \{0,1,\dots,11\}\), such that the induced edge labels are distinct. Hence, grac\((G)=11\). ◻
Interestingly, for the labeling of \(G= \overline{K_2} + (K_2 \cup K_2)\) in Figure 3(a), one can see that the highest edge label obtained is \(10\). Hence, we can conclude that grac\((G)\) need not be obtained as an edge label, in a labeling which realizes grac\((G)\). This settles the Open Problem 1.17.
Again from the labeling of \(G= \overline{K_2} + (K_2 \cup K_2)\) in Figure 3(a), one can see that, \(ecg(G)=m(G)=10\) and hence, \(q=ecg(G)\). But by Theorem 3.2, \(G\) is not graceful. Hence, we can conclude that, \(q=ecg(G)\) does not imply that \(G\) is graceful. This settles the Open Problem 1.18
Also, grac\((G)-q = 1\) while \(q-ecg(G)=0\). Hence, we can see that it is not true in general that, grac\((G)-q = q-ecg(G)\). This settles the Open Problem 1.19.
Summing up, we observe that in [7] and [8], it was anticipated that \(q-ecg(G)\) or \(q-m(G)\) could possibly be a new measure of gracefulness of a graph and this idea was further promoted in [3]. From our discussions and in conjunction with Remark 1.20, we can see that \(q-ecg(G)\) may not be suitable as a good measure of gracefulness.
\(\overline{K_2} + (K_2 \cup K_2)\) has other properties like the fact that it is pseudo graceful. These can be examined further. As yet there are no known additively graceful labelings of signed graphs on \(K_p\) for \(p\geq 11\). Additively graceful signed paths and cycles have been characterized in [2], but the problem of characterizing additively graceful labelings of signed graphs on \(K_p\) remains open.