The edge-bandwidth of a graph \( G \) is the smallest number \( b \) for which there exists an injective labeling of \( E(G) \) with integers such that the difference between the labels of any pair of adjacent edges is at most \( b \). The edge-bandwidth of a torus (a product of two cycles) has been computed within an additive error of \( 5 \). In this paper, we improve the upper bound, reducing the error to \( 3 \).

Let \( G \) be a connected graph of order 3 or more and \( c : E(G) \to \mathbb{Z}_k \) (\( k \geq 2 \)) an edge coloring of \( G \) where adjacent edges may be colored the same. The color sum \( s(v) \) of a vertex \( v \) of \( G \) is the sum in \( \mathbb{Z}_k \) of the colors of the edges incident with \( v \). An edge coloring \( c \) is a modular neighbor-distinguishing \( k \)-edge coloring of \( G \) if \( s(u) \neq s(v) \) in \( \mathbb{Z}_k \) for all pairs \( u, v \) of adjacent vertices of \( G \). The modular chromatic index \( \chi_m'(G) \) of \( G \) is the minimum \( k \) for which \( G \) has a modular neighbor-distinguishing \( k \)-edge coloring. For every graph \( G \), it follows that \( \chi_m'(G) \geq \chi(G) \). In particular, it is shown that if \( G \) is a graph with \( \chi(G) \equiv 2 \mod 4 \) for which every proper \( \chi(G) \)-coloring of \( G \) results in color classes of odd size, then \( \chi_m'(G) > \chi(G) \). The modular chromatic indices of several well-known classes of graphs are determined. It is shown that if \( G \) is a connected bipartite graph, then \( 2 \leq \chi_m'(G) \leq 3 \) and it is determined when each of these two values occurs. There is a discussion on the relationship between \( \chi_m'(G) \) and \( \chi_m'(H) \) when \( H \) is a subgraph of \( G \).

Let \( [n]^* \) denote the set of integers \(\{-\frac{n-1}{2}, \ldots, \frac{n+1}{2}\}\) if \( n \) is odd, and \(\{-\frac{n}{2}, \ldots, \frac{n}{2}\} \setminus \{0\}\) if \( n \) is even. A super edge-graceful labeling \( f \) of a graph \( G \) of order \( p \) and size \( q \) is a bijection \( f : E(G) \to [q]^* \), such that the induced vertex labeling \( f^* \) given by \( f^*(u) = \sum_{uv \in E(G)} f(uv) \) is a bijection \( f^* : V(G) \to [p]^* \). A graph is super edge-graceful if it has a super edge-graceful labeling. We prove that all complete tripartite graphs \( K_{a,b,c} \), except \( K_{1,1,2} \), are super edge-graceful.

Suppose \( G \) is a graph with vertex set \( V(G) \) and edge set \( E(G) \), and let \( A \) be an additive Abelian group. A vertex labeling \( f: V(G) \to A \) induces an edge labeling \( f^*: E(G) \to A \) defined by \( f^*(xy) = f(x) + f(y) \). For \( a \in A \), let \( n_a(f) \) and \( m_a(f) \) be the number of vertices \( v \) and edges \( e \) with \( f(v) = a \) and \( f^*(e) = a \), respectively. A graph \( G \) is \( A \)-cordial if there exists a vertex labeling \( f \) such that \( |n_a(f) – n_b(f)| \leq 1 \) and \( |m_a(f) – m_b(f)| \leq 1 \) for all \( a, b \in A \). When \( A = \mathbb{Z}_k \), we say that \( G \) is \( k \)-cordial instead of \( \mathbb{Z}_k \)-cordial. In this paper, we investigate certain regular graphs and ladder graphs that are \( 4 \)-cordial and we give a complete characterization of the \( 4 \)-cordiality of the complete \( 4 \)-partite graph. An open problem about which complete multipartite graphs are not \( 4 \)-cordial is given.

The square \( G^2 \) of a graph \( G \) is a graph with the same vertex set as \( G \) in which two vertices are joined by an edge if their distance in \( G \) is at most two. For a graph \( G \), \( \chi(G^2) \), which is also known as the distance two coloring number of \( G \), is studied. We study coloring the square of grids \( P_m \Box P_n \), cylinders \( P_m \Box C_n \), and tori \( C_m \Box C_n \). For each \( m \) and \( n \) we determine \( \chi((P_m \Box P_n)^2) \), \( \chi((P_m \Box C_n)^2) \), and in some cases \( \chi((C_m \Box C_n)^2) \) while giving sharp bounds to the latter. We show that \( \chi((C_m \Box C_n)^2) \) is at most \( 8 \) except when \( m = n = 3 \), in which case the value is \( 9 \). Moreover, we conjecture that for every \( m \) (\( m \geq 5 \)) and \( n \) (\( n \geq 5 \)), we have \( 5 \leq \chi((C_m \Box C_n)^2) \leq 7 \).

Given any positive integer \( k \), a \((p,q)\)-graph \( G = (V, E) \) is strongly \( k \)-indexable if there exists a bijection \( f : V \to \{0,1,2,\ldots,p – 1\} \) such that \( f^+(E(G)) = \{k,k+1,k+2,\ldots,k+q-1\} \) where \( f^+(uv) = f(u) + f(v) \) for any edge \( uv \in E \); in particular, \( G \) is said to be strongly indexable when \( k = 1 \). For any strongly \( k \)-indexable \((p, q)\)-graph \( G \), \( q \leq 2p – 3 \) and if, in particular, \( q = 2p – 3 \) then \( G \) is called a maximal strongly indexable graph. In this paper, necessary conditions for an Eulerian \((p,q)\)-graph \( G \) to be strongly \( k \)-indexable have been obtained. Our main focus is to initiate a study of maximal strongly indexable graphs and, on this front, we strengthen a result of G. Ringel on certain outerplanar graphs.

Let \( G \) be a connected graph. A vertex \( r \) resolves a pair \( u,v \) of vertices of \( G \) if \( u \) and \( v \) are different distances from \( r \). A set \( R \) of vertices of \( G \) is a resolving set for \( G \) if every pair of vertices of \( G \) is resolved by some vertex of \( R \). The smallest cardinality of a resolving set is called the metric dimension of \( G \). A vertex \( r \) strongly resolves a pair \( u,v \) of vertices of \( G \) if there is some shortest \( u-r \) path that contains \( v \) or a shortest \( v-r \) path that contains \( u \). A set \( S \) of vertices of \( G \) is a strong resolving set for \( G \) if every pair of vertices of \( G \) is strongly resolved by some vertex of \( S \); and the smallest cardinality of a strong resolving set of \( G \) is called the strong dimension of \( G \). The problems of finding the metric dimension and strong dimension are NP-hard. Both the metric and strong dimension can be found efficiently for trees. In this paper, we present efficient solutions for finding the strong dimension of distance-hereditary graphs, a class of graphs that contains the trees.

An efficient method for generating level sequence representations of rooted trees in a well-defined order was developed by Beyer and Hedetniemi. In this paper, we extend Beyer and Hedetniemi’s approach to produce an algorithm for parallel generation of rooted trees. This is accomplished by defining the lexicographic distance between two rooted trees to be the number of rooted trees between them in the ordering of trees produced by the Beyer and Hedetniemi algorithm. Formulas are provided for the lexicographic distance between rooted trees with certain structures. In addition, we present algorithms for ranking and unranking rooted trees based on the ordering of the trees that is induced by the Beyer and Hedetniemi generation algorithm.

A fall coloring of a graph \( G \) is a color partition of the vertex set of \( G \) in such a way that every vertex of \( G \) is a colorful vertex in \( G \) (that is, it has at least one neighbor in each of the other color classes). The fall coloring number \( \chi_f(G) \) of \( G \) is the minimum size of a fall color partition of \( G \) (when it exists). In this paper, we show that the Mycielskian \( \mu(G) \) of any graph \( G \) does not have a fall coloring and that the generalized Mycielskian \( \mu_m(G) \) of a graph \( G \) may or may not have a fall coloring. More specifically, we show that if \( G \) has a fall coloring, then \( \mu_{3m}(G) \) has also a fall coloring for \( m \geq 1 \), and that \( \chi_f(\mu_{3m}(G)) \leq \chi_f(G) + 1 \).

For a positive integer \( d \), a set \( S \) of positive integers is \({difference \; d -free}\) if \( |x – y| \neq d \) for all \( x, y \in S \). We consider the following Ramsey-theoretical question: Given \( d, k, r \in \mathbb{Z}^+ \), what is the smallest integer \( n \) such that every \( r \)-coloring of \( [1, n] \) contains a monochromatic \( k \)-element difference \( d \)-free set? We provide a formula for this \( n \). We then consider the more general problem where the monochromatic \( k \)-element set must avoid a given set of differences rather than just one difference.