A \((p, g)\)-graph \(G\) is Euclidean if there exists a bijection \(f: V \to \{1, 2, \ldots, p\}\) such that for any induced \(C_3\)-subgraph \(\{v_1, v_2, v_3\}\) in \(G\) with \(f(v_1) < f(v_2) < f(v_3)\), we have that \(f(v_1) + f(v_2) > f(v_3)\). The Euclidean Deficiency of a graph \(G\) is the smallest integer \(k\) such that \(G \cup N_k\) is Euclidean. We study the Euclidean Deficiency of one-point union and one-edge union of complete graphs.

The dominating set of a graph \(G\) is a set of vertices \(D\) such that for every \(v \in V(G)\) either \(v \in D\) or \(v\) is adjacent to a vertex in \(D\). The domination number, denoted \(\gamma(G)\), is the minimum number of vertices in a dominating set. In 1998, Haynes and Slater [1] introduced paired-domination. Building on paired-domination, we introduce 3-path domination. We define a 3-path dominating set of \(G\) to be \(D = \{ Q_1,Q_2,\dots , Q_k\, |\:Q_i \text{ is a 3-path}\}\) such that the vertex set \(V(D) = V(Q_1) \cup V(Q_2) \cup \dots \cup V(Q_k)\) is a dominating set. We define the 3-path domination number, denoted by \(\gamma_{P_3}(G)\), to be the minimum number of 3-paths needed to dominate \(G\). We show that the 3-path domination problem is NP-complete. We also prove bounds on \(\gamma_{P_3}(G)\) and improve those bounds for particular families of graphs such as Harary graphs, Hamiltonian graphs, and subclasses of trees. In general, we prove \(\gamma_{P_3}(G) \leq \frac{n}{3}\).

Two colorings have been introduced recently where an unrestricted coloring \(c\) assigns nonempty subsets of \([k]=\{1,\ldots,k\}\) to the edges of a (connected) graph \(G\) and gives rise to a vertex-distinguishing vertex coloring by means of set operations. If each vertex color is obtained from the union of the incident edge colors, then \(c\) is referred to as a strong royal coloring. If each vertex color is obtained from the intersection of the incident edge colors, then \(c\) is referred to as a strong regal coloring. The minimum values of \(k\) for which a graph \(G\) has such colorings are referred to as the strong royal index of \(G\) and the strong regal index of \(G\) respectively. If the induced vertex coloring is neighbor distinguishing, then we refer to such edge colorings as royal and regal colorings. The royal chromatic number of a graph involves minimizing the number of vertex colors in an induced vertex coloring obtained from a royal coloring. In this paper, we provide new results related to these two coloring concepts and establish a connection between the corresponding chromatic parameters. In addition, we establish the royal chromatic number for paths and cycles.

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.