An \(L(2,1)\)-labeling of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to the set of all nonnegative integers such that \(|f(x)-f(y)|\geq 2\quad\text{if}\quad d_G(x,y)=1\) and \(|f(x)-f(y)|\geq 1\quad\text{if}\quad d_G(x,y)=2\). The \(L(2,1)\)-labeling problem is to find the smallest number \(\lambda(G)\) such that there exists an \(L(2,1)\)-labeling function with no label greater than \(\lambda(G)\). Motivated by the channel assignment problem introduced by Hale, the \(L(2,1)\)-labeling problem has been extensively studied in the past decade. In this paper, we study this concept for digraphs. In particular, results on ditrees are given.

Let \(G\) be a simple graph with vertex set \(V\) and edge set \(E\). A vertex labeling \(\overline{f}: V \to \{0,1\}\) induces an edge labeling \(\overline{f}: E \to \{0,1\}\) defined by \(f(uv) = |f(u) – f(v)|\) .Let \(v_f(0),v_f(1)\) denote the number of vertices \(v\) with \(f(v) = 0\) and \(f(v) = 1\) respectively. Let \(e_f(0),e_f(1)\) be similarly defined. A graph is said to be cordial if there exists a vertex labeling \(f\) such that \(|v_f(0) – vf(1)| \leq 1\) and \(|e_f(0) – e_f(1)| \leq 1\).

A \(t\)-uniform homeomorph \(P_t(G)\) of \(G\) is the graph obtained by replacing all edges of \(G\) by vertex disjoint paths of length \(t\). In this paper we investigate the cordiality of \(P_t(G)\), when \(G\) itself is cordial. We find, wherever possible, a cordial labeling of \(P_t(G)\), whose restriction to \(G\) is the original cordial labeling of \(G\) and prove that for a cordial graph \(G\) and a positive integer \(t\), (1) \(P_t(G)\) is cordial whenever \(t\) is odd, (2) for \(t \equiv 2 \pmod{4}\) a cordial labeling \(g\) of \(G\) can be extended to a cordial labeling \(f\) of \(P_t(G)\) iff \(e_0\) is even, (3) for \(t \equiv 0 \pmod{4}\), a cordial labeling \(g\) of \(G\) can be extended to a cordial labeling \(f\) of \(P_t(G)\) iff \(e_1\) is even.

The domination graph \(dom(D)\) of a digraph \(D\) has the same vertex set as \(D\), and \(\{u,v\}\) is an edge if and only if for every \(w\), either \((u,w)\) or \((v,w)\) is an arc of \(D\). In earlier work we have shown that if \(G\) is a domination graph of a tournament, then \(G\) is either a forest of caterpillars or an odd cycle with additional pendant vertices or isolated vertices. We have also earlier characterized those connected graphs and forests of non-trivial caterpillars that are domination graphs of tournaments. We complete the characterization of domination graphs of tournaments by describing domination graphs with isolated vertices.

It is proved that the \(n\)-cone \(C_m \vee K_n^c\) is graceful for any \(n \geq 1\) and \(m = 0\) or \(3 \pmod{12}\). The gracefulness of the following \(n\)-cones is also established: \(C_4 \vee K_n^c\), \(C_5 \vee K_2^c\), \(C_7 \vee K_n^c\), \(C_9 \vee K_2^c\), \(C_{11} \vee K_n^c\), \(C_{19} \vee K_n^c\). This partially answers the question of gracefulness of \(n\)-cones which is listed as an open problem in the survey article by J.A. Gallian.

We tackle the problem of estimating the Shannon capacity of cycles of odd length. We present some strategies which allow us to find tight bounds on the Shannon capacity of cycles of various odd lengths, and suggest that the difficulty of obtaining a general result may be related to different behaviours of the capacity, depending on the “structure” of the odd integer representing the cycle length. We also describe the outcomes of some experiments, from which we derive the evidence that the Shannon capacity of odd cycles is extremely close to the value of the Lovasz theta function.