A ranking on a graph \(G\) is a function \(f: V(G) \rightarrow \left\{1, 2, \ldots, k \right\}\) with the following restriction: if \(f(u)=f(v)\) for any \(u, v \in V(G)\), then on every \(uv\) path in \(G\), there exists a vertex \(w\) with \(f(w) > f(u)\). The optimality of a ranking is conventionally measured in terms of the \(l_{\infty}\) norm of the sequence of labels produced by the ranking. In \cite{jacob2017lp} we compared this conventional notion of optimality with the \(l_p\) norm of the sequence of labels in the ranking for any \(p \in [0,\infty)\), showing that for any non-negative integer \(c\) and any non-negative real number \(p\), we can find a graph such that the sets of \(l_p\)-optimal and \(l_{\infty}\)-optimal rankings are disjoint. In this paper we identify some graphs whose set of \(l_p\)-optimal rankings and set of \(l_{\infty}\)-optimal rankings overlap. In particular, we establish that for paths and cycles, if \(p>0\) then \(l_p\) optimality implies \(l_{\infty}\) optimality but not the other way around, while for any complete multipartite graph, \(l_p\) optimality and \(l_{\infty}\) optimality are equivalent.

We use a representation for the spanning tree where a parent function maps non-root vertices to vertices. Two spanning trees are defined to be adjacent if their function representations differ at exactly one vertex. Given a graph \(G\), we show that the graph \(H\) with all spanning trees of \(G\) as vertices and any two vertices being adjacent if and only if their parent functions differ at exactly one vertex is connected.

A \((0,1)\)-labeling of a set is said to be friendly if the number of elements of the set labeled 0 and the number labeled 1 differ by at most 1. Let \(g\) be a labeling of the edge set of a graph that is induced by a labeling \(f\) of the vertex set. If both \(g\) and \(f\) are friendly then \(g\) is said to be a cordial labeling of the graph. We extend this concept to directed graphs and investigate the cordiality of directed graphs. We show that all directed paths and all directed cycles are cordial. We also discuss the cordiality of oriented trees and other digraphs.

We propose and study the problem of finding the smallest nonnegative integer \(s\) such that a GDD\((m, n, 3; 0, \lambda)\) can be embedded into a BIBD\((mn + s, 3, \lambda)\). We find the values of \(s\) for all cases except for the case where \(n \equiv 5 \pmod{6}\) and \(m \equiv 1, 3 \pmod{6}\) and \(m \ge 3\), which remains as an open problem.

A simple graph \(G\) with \(p\) vertices is said to be vertex-Euclidean if there exists a bijection \(f: V(G) \rightarrow \{1, 2, \ldots, p\}\) such that \(f(v_1) + f(v_2) > f(v_3)\) for each \(C_3\)-subgraph with vertex set \(\{v_1, v_2, v_3\}\), where \(f(v_1) < f(v_2) < f(v_3)\). More generally, the vertex-Euclidean deficiency of a graph \(G\) is the smallest integer \(k\) such that \(G \cup N_k\) is vertex-Euclidean. To illustrate the idea behind this new graph labeling problem, we study the vertex-Euclidean deficiency of two new families of graphs called the complete fan graphs and the complete wheel graphs. We also explore some related problems, and pose several research topics for further study.

A signed magic rectangle \(SMR(m, n; r, s)\) is an \(m \times n\) array with entries from \(X\), where \(X = \{0, \pm1, \pm2, \ldots, \pm(ms – 1)/2\}\) if \(mr\) is odd and \(X = \{\pm1, \pm2, \ldots, \pm mr/2\}\) if \(mr\) is even, such that precisely \(r\) cells in every row and \(s\) cells in every column are filled, every integer from set \(X\) appears exactly once in the array, and the sum of each row and of each column is zero. In this paper, we prove that a signed magic rectangle \(SMR(m, n; r, 2)\) exists if and only if \(m = 2\) and \(n = r \equiv 0, 3 \pmod{4}\) or \(m, r \geq 3\) and \(mr = 2n\).

A graph \(G\) is asymmetric if its automorphism group is trivial. Asymmetric graphs were introduced by Erdős and Rényi [1]. They suggested the problem of starting with an asymmetric graph and removing some number, \(r\), of edges and/or adding some number, \(s\), of edges so that the resulting graph is non-asymmetric. Erdős and Rényi defined the degree of asymmetry of a graph to be the minimum value of \(r+s\). In this paper, we consider another property that measures how close a given non-asymmetric graph is to being asymmetric. Brewer et al defined the asymmetric index of a graph \(G\), denoted \(ai(G)\) is the minimum of \(r+s\) so that the resulting graph \(G\) is asymmetric [2]. It is noted that \(ai(G)\) is only defined for graphs with at least six vertices. We investigate the asymmetric index of both connected and disconnected graphs including paths, cycles, and grids, with the addition of up to two isolated vertices. Furthermore for a graph in these families \(G\) we determine the number of labelled asymmetric graphs that can be obtained by adding or removing \(ai(G)\) edges. This leads to the related question: Given a graph \(G\) where \(ai(G)=1\), what is the probability that for a randomly chosen edge \(e\), that \(G-e\) will be asymmetric? A graph is called minimally non-asymmetric if this probability is \(1\). We give a construction of infinite families of minimally non-asymmetric graphs.

A graph \(G\) is said to arrow the graphs \(F\) and \(H\), written \(G \rightarrow (F, H)\), if every red-blue coloring of \(G\) results in a red \(F\) or a blue \(H\). The primary question has been determining graphs \(G\) for which \(G \rightarrow (F, H)\). If we consider the version for which \(F = H\), then we can ask a different question: Given a graph \(G\), can we determine all graphs \(F\) such that \(G \rightarrow (F, F)\), or simply \(G \rightarrow F\)? We call this set of graphs the down-arrow Ramsey set of \(G\), or \(\downarrow G\). The down-arrow Ramsey set of cycles, paths, and small complete graphs are determined. Graph ideals and graph intersections are introduced and a method for computing down-arrow Ramsey sets is described.

We use a dynamic programming algorithm to establish a new lower bound on the domination number of complete cylindrical grid graphs of the form \(C_n\square P_m\), that is, the Cartesian product of a path and a cycle, when \(n\equiv 2\pmod{5}\), and we establish a new upper bound equal to the lower bound, thus computing the exact domination number for these graphs.

In this paper, we address computational questions surrounding the enumeration of non-isomorphic André planes for any prime power order \(q\). We are particularly focused on providing a complete enumeration of all such planes for relatively small orders (up to 125), as well as developing computationally efficient ways to count the number of isomorphism classes for other orders where enumeration is infeasible. André planes of all dimensions over their kernel are considered.