A graceful difference labeling (gdl for short) of a directed graph \(G\) with vertex set \(V\) is a bijection \(f:V\rightarrow\{1,\ldots,\vert V\vert\}\) such that, when each arc $uv$ is assigned the difference label \(f(v)-f(u)\), the resulting arc labels are distinct. We conjecture that all disjoint unions of circuits have a gdl, except in two particular cases. We prove partial results which support this conjecture.
A graph labeling is the assignment of labels, traditionally represented by integers, to the vertices or edges, or both, of a graph, subject to certain conditions. As mentioned in the survey by Gallian [1], more than one thousand papers are devoted to this subject. Among all variations, the most popular and studied graph labelings are the \(\beta\)-valuations introduced by Rosa in 1966 [2], and later called graceful labelings by Golomb [3]. Formally, given a graph \(G\) with vertex set \(V\) and \(q\) edges, a graceful labeling of \(G\) is an injection \(f:V\rightarrow\{0,1,\ldots,q\}\) such that, when each edge \(uv\) is assigned the label \(\vert f(v)-f(u)\vert\), the resulting edge labels are distinct. In other words, the vertices are labeled using integers in \(\{0,1,\ldots,q\}\), and these vertex labels induce an edge labeling from \(1\) to \(q\). The famous Ringel-Kotzig conjecture, also known as the graceful labeling conjecture, hypothesizes that all trees are graceful. It is the focus of many papers and is still open, even for some very restricted graph classes such that trees with 5 leaves, and trees with diameter 6. The survey by Gallian [1] lists several papers dealing with graceful labelings of particular classes of graphs, such that the disjoint union of cliques, the disjoint union of cycles, and the union of cycles with one common vertex.
For a directed graph with vertex set \(V\) and \(q\) edges, a graceful labeling of \(G\) is an injection \(f:V\rightarrow\{0,1,\ldots,q\}\) such that, when each arc (i.e., directed edge) \(uv\) is assigned the label \((f(v)-f(u))\ (mod\ q+1)\), the resulting arc labels are distinct. As mentioned in [1] and [4], most results and conjectures on graceful labelings of directed graphs concern directed cycles, the disjoint union of directed cycles, and the union of directed cycles with one common vertex or one common arc. In particular, it is proved that \(n\overrightarrow{\bf C_3}\), the disjoint union of \(n\) copies of the directed cycle with three vertices, has a graceful labeling only if \(n\) is even. However, it is not known whether this necessary condition is also sufficient.
In this paper, we study graceful difference labelings of directed graphs, which are defined as follows. A graceful difference labeling (gdl for short) of a directed graph \(G=(V,A)\) is a bijection \(f:V\rightarrow\{1,\ldots,\vert V\vert\}\) such that, when each arc \(uv\) is assigned the difference label \(f(v)-f(u)\), the resulting arc labels are distinct. The absolute value \(|f(v)-f(u)|\) is called the magnitude of arc \(uv\), while \(f(v)\) is the vertex label of \(v\). Note that in a gdl of \(G\), two arcs \(uv\) and \(u’v’\) may have the same magnitude \(|f(v)-f(u)|=|f(v’)-f(u’)|\) but their difference labels must then be opposite, i.e., \(f(v)-f(u)=-(f(v’)-f(u’))\).
Given two graphs \(G_i=(V_i,A_i)\) and \(G_j=(V_j,A_j)\) with \(V_i\cap V_j=\emptyset,\) their disjoint union, denoted \(G_i+G_j\), is the graph with vertex set \(V_i\cup V_j\) and arc set \(A_i\cup A_j\). By \(pG\) we denote the disjoint union of \(p\) copies of \(G\). For \(k\ge 2\) we denote by \(\overrightarrow{\bf C_k}\) a circuit on \(k\) vertices isomorphic to the directed graph with vertex set \(V=\{v_1,\ldots, v_k\}\) and arc set \(A=\{v_iv_{i+1}:\ 1\le i< k\}\cup\{v_kv_1\}\). The circuit \(\overrightarrow{\bf C_3}\) is also called a directed triangle, or simply a triangle. For all graph theoretical terms not defined here the reader is referred to [5].
Not every directed graph has a gdl. Indeed, a necessary condition for \(G=(V,A)\) to have a gdl is \(\vert A\vert\le2(\vert V\vert-1)\). Nevertheless this condition is not sufficient since, for example, \(\overrightarrow{\bf C_3}\) has no gdl. Indeed, all bijections \(f:V\rightarrow\{1,2,3\}\) induce two difference labels equal to 1, or two equal to -1. As a second example, \(\overrightarrow{\bf C_2}+\overrightarrow{\bf C_3}\) has no gdl. Indeed:
