In this paper we determine, or give lower and upper bounds on, the 2-dipath and oriented L(2, 1)-span of the family of planar graphs, planar graphs with girth 5, 11, 16, partial k-trees, outerplanar graphs and cacti.

This paper gives a shortest path algorithm for CFG (context free grammar) labeled and weighted digraphs where edge weights may be positive or negative, but negative-weight cycles are not allowed in the underlying unlabeled graph. These results build directly on an algorithm of Barrett et al. [SIAM J. Comput.30 (2000) 809–837]. In addition to many other results, they gave a shortest path algorithm for CFG labeled and weighted digraphs where all edges are nonnegative. Our algorithm is based closely...

A graph G of size q is graceful if there exists an injective function f:V(G)→ 0,1,...,q such that each edge uv of G is labeled |f(u)-f(v)| and the resulting edge labels are distinct. Also, a (p,q) graph G with q ≥ p is harmonious if there exists an injective function $f:V\left(G\right)\to Z_q$ such that each edge uv of G is labeled f(u) + f(v) mod q and the resulting edge labels are distinct, whereas G is felicitous if there exists an injective function $f:V\left(G\right)\to Z_{q+1}$ such that each edge uv of G is labeled f(u) + f(v) mod q and the...

Motivated by problems in radio channel assignments, we consider radio k-labelings of graphs. For a connected graph G and an integer k ≥ 1, a linear radio k-labeling of G is an assignment f of nonnegative integers to the vertices of G such that $|f\left(x\right)-f\left(y\right)|\ge k+1-d_G(x,y)$, for any two distinct vertices x and y, where $d_G(x,y)$ is the distance between x and y in G. A cyclic k-labeling of G is defined analogously by using the cyclic metric on the labels. In both cases, we are interested in minimizing the span of the labeling. The linear...

We study identities of the form $$L_{x_0}{\varphi }_1\cdots {\varphi }_n{R}_{x_{n+1}}=R_{x_{n+1}}{\varphi }_{\sigma \left(1\right)}\cdots {\varphi }_{\sigma \left(n\right)}{L}_{x_0}$$ in quasigroups, where $n\ge 1$, $\sigma$ is a permutation of $\{1,...,n\}$, and for each $i$, ${\varphi }_i$ is either $L_{x_i}$ or $R_{x_i}$. We prove that in a quasigroup, every such identity implies commutativity. Moreover, if $\sigma$ is chosen randomly and uniformly, it also satisfies associativity with probability approaching $1$ as $n\to \infty$.