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.

The covering number for a subset of leaves in a finite rooted tree is defined as the number of subtrees which remain after deleting all the paths connecting the root and the other leaves. We find the formula for the total sum (hence the average) of the covering numbers for a given subset of labeled leaves over all unordered binary trees with \( n \) leaves.