Given a graph G with p vertices, q edges and a positive integer k, a k-sequentially additive labeling of G is an assignment of distinct numbers k,k+1,k+2,...,k+p+q-1 to the p+q elements of G so that every edge uv of G receives the sum of the numbers assigned to the vertices u and v. A graph which admits such an assignment to its elements is called a k-sequentially additive graph. In this paper, we give an upper bound for k with respect to which the given graph may possibly be k-sequentially additive...

Hovey introduced A-cordial labelings in [4] as a simultaneous generalization of cordial and harmonious labelings. If A is an abelian group, then a labeling f: V(G) → A of the vertices of some graph G induces an edge-labeling on G; the edge uv receives the label f(u) + f(v). A graph G is A-cordial if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one. Research on A-cordiality...

A $(p,q)$-sigraph $S$ is an ordered pair $(G,s)$ where $G=(V,E)$ is a $(p,q)$-graph and $s$ is a function which assigns to each edge of $G$ a positive or a negative sign. Let the sets $E^{+}$ and $E^{-}$ consist of $m$ positive and $n$ negative edges of $G$, respectively, where $m+n=q$. Given positive integers $k$ and $d$, $S$ is said to be $(k,d)$-graceful if the vertices of $G$ can be labeled with distinct integers from the set $\{0,1,\cdots ,k+(q-1\left)d\right\}$ such that when each edge $uv$ of $G$ is assigned the product of its sign and the absolute difference of the integers assigned to $u$ and $v$ the...

In our earlier paper [9], generalizing the well known notion of graceful graphs, a $(p,m,n)$-signed graph $S$ of order $p$, with $m$ positive edges and $n$ negative edges, is called graceful if there exists an injective function $f$ that assigns to its $p$ vertices integers $0,1,\cdots ,q=m+n$ such that when to each edge $uv$ of $S$ one assigns the absolute difference $\left|f\right(u)-f(v\left)\right|$ the set of integers received by the positive edges of $S$ is $\{1,2,\cdots ,m\}$ and the set of integers received by the negative edges of $S$ is $\{1,2,\cdots ,n\}$. Considering the conjecture therein that all...

By a hamiltonian coloring of a connected graph $G$ of order $n\ge 1$ we mean a mapping $c$ of $V\left(G\right)$ into the set of all positive integers such that $|c\left(x\right)-c\left(y\right)|\ge n-1-D_G(x,y)$ (where $D_G(x,y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x,y\in G$. In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order $n\ge 5$ with circumference $n-2$.

For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)+2$ for every positive integer n, where ac’(Pₙ) denotes the nearly antipodal chromatic number of Pₙ. In this paper we show that $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)-n/2-⎣10/n⎦+7$ if n is even positive integer and n ≥ 10, and $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)-(n-1)/2-⎣13/n⎦+8$ if n is odd positive integer and n ≥ 13. For all even positive integers n ≥ 10 and all odd positive integers n ≥ 13, these results improve the upper bounds for nearly antipodal chromatic number of Pₙ.

Let $G$ be a graph, and $\lambda$ the smallest integer for which $G$ has a nowhere-zero $\lambda$-flow, i.e., an integer $\lambda$ for which $G$ admits a nowhere-zero $\lambda$-flow, but it does not admit a $(\lambda -1)$-flow. We denote the minimum flow number of $G$ by $\Lambda \left(G\right)$. In this paper we show that if $G$ and $H$ are two arbitrary graphs and $G$ has no isolated vertex, then $\Lambda (G\vee H)\le 3$ except two cases: (i) One of the graphs $G$ and $H$ is $K_2$ and the other is $1$-regular. (ii) $H=K_1$ and $G$ is a graph with at least one isolated vertex or a component whose every block is an...

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

A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (and consecutive) positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we prove that any balanced bipartite graph with minimum degree greater than |V(G)|/4 ≥ 2 is magic. A similar result is presented for supermagic regular bipartite graphs.

Necessary and sufficient conditions for a graph $G$ that its power $G^i$, $i\ge 2$, is a magic graph and one consequence are given.