The genus of a graph \(G\), denoted by \(\gamma(G)\), is the minimum genus of an orientable surface in which the graph can be embedded. In the paper, we use the Joint Tree Model to immerse a graph on the plane and obtain an associated polygon of the graph. Along the way, we construct a genus embedding of the edge disjoint union of \(K\) and \(H\), and solve Michael Stiebitz’s proposed conjecture: Let \(G\) be the edge disjoint union of a complete graph \(K\) and an arbitrary graph \(H\). Let \(H’\) be the graph obtained from \(H\) by contracting the set \(V(X)\) to a single vertex. Then

\[\gamma(K) + \gamma(H’) \leq \gamma(G).\]

We investigate brother avoiding round robin doubles tournaments and construct several infinite families. We show that there is a BARRDT(\(x\)) that is not a SAMDRR(\(n\)) for all \(n > 4\).

A digraph \(D(V, E)\) is said to be graceful if there exists an injection \(f: V(G) \to \{0, 1, \ldots, |E|\}\) such that the induced function \(f’: E(G) \to \{1, 2, \ldots, |E|\}\) which is defined by \(f'(u, v) = [f(v) – f(u)] \pmod{|E| + 1}\) for every directed edge \((u, v)\) is a bijection. Here, \(f\) is called a graceful labeling (graceful numbering) of \(D(V, E)\), while \(f’\) is called the induced edge’s graceful labeling of \(D\). In this paper, we discuss the gracefulness of the digraph \(n – \overrightarrow{C}_m\), and prove that \(n – \overrightarrow{C}_m\) is a graceful digraph for \(m = 4, 6, 8, 10\) and even \(n\).

In this note, we consider relative difference sets with the parameter \((m, 2, m-1, \frac{m-2}{2})\) in a group \(G\) relative to a subgroup \(N\). In the splitting case, \(G = H \times N\), we give a lower bound for the size of the commutator group \(H’\), and we show that \(H\) cannot have a homomorphic image which is generalized dihedral. In the non-splitting case, we prove that there is no \((2n, 2, 2n-1, n-1)\) relative difference set in a generalized dihedral group of order \(4n\), \(n > 1\).

Let \(P_n\) be a path with \(n\) vertices. \(P_n^k\), the \(k\)-th power of the path \(P_n\), is a graph on the same vertex set as \(P_n\), and the edges that join all vertices \(x\) and \(y\) if and only if the distance between them is at most \(k\). In this paper, the crossing numbers of \(P_n^k\) are studied. Drawings of \(P_n^k\) are presented and proved to be optimal for the case \(n \leq 8\) and for the case \(k \leq 4\).

A graph is said to be locally grid if the structure around each of its vertices is a \(3 x 3\) grid. As a follow up of the research initiated in \([8]\) and \([9]\) we prove that most locally grid graphs are uniquely determined by their Tutte polynomial.

Let \(P(G, \lambda)\) be the chromatic polynomial of a graph \(G\). A graph \(G\) is chromatically unique if for any graph \(H\), \(P(H, \lambda) = P(G, \lambda)\) implies \(H\) is isomorphic to \(G\). In his Ph.D. thesis, Zhao [Theorems 5.4.2 and 5.4.3] proved that for any positive integer \(t \geq 3\), the complete \(t\)-partite graphs \(K(p – k, p, p, \ldots, p)\) with \(p \geq k+2 \geq 4\) and \(K(p-k, p – 1, p, \ldots, p)\) with \(p \geq 2k \geq 4\) are chromatically unique. In this paper, by expanding the technique employed by Zhao, we prove that the complete \(t\)-partite graph \(K(p-k,\underbrace{ p -1, \ldots, p-1}, \underbrace{p, \ldots, p})\) is chromatically unique for integers \(p \geq k+2 \geq 4\) and \(t \geq d+3 \geq 3\).

We present a block diagonalization method for the adjacency matrices of two types of covering graphs. A graph \(Y\) is a covering graph of a base graph \(X\) if there exists an onto graph map \(\pi: Y \to X\) such that for each \(x \in X\) and for each \(y \in \{y \mid \pi(y) = x\}\), the collection of vertices adjacent to \(y\) maps onto the collection of vertices adjacent to \(x \in X\). The block diagonalization method requires the irreducible representations of the Galois group of \(Y\) over \(X\). The first type of covering graph is the Cayley graph over the finite ring \(\mathbb{Z}/p^n\mathbb{Z}\). The second type of covering graph resembles large lattices with vertices \(\mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}\) for large \(n\). For one lattice, the block diagonalization method allows us to obtain explicit formulas for the eigenvalues of its adjacency matrix. We use these formulas to analyze the distribution of its eigenvalues. For another lattice, the block diagonalization method allows us to find non-trivial bounds on its eigenvalues.

Broadcast domination in graphs is a variation of domination in which different integer weights are allowed on vertices and a vertex with weight \(k\) dominates its distance \(k\)-neighborhood. A distribution of weights on vertices of a graph \(G\) is called a dominating broadcast, if every vertex is dominated by some vertex with positive weight. The broadcast domination number \(\gamma_b(G)\) of a graph \(G\) is the minimum weight (the sum of weights over all vertices) of a dominating broadcast of \(G\). In this paper, we prove that for a connected graph \(G\), \(\gamma_b(G) \geq \lceil{2\text{rad}(G)}/{3}\rceil\). This general bound and a newly introduced concept of condensed dominating broadcast are used in obtaining sharp upper bounds for broadcast domination numbers of three standard graph products in terms of broadcast domination numbers of factors. A lower bound for a broadcast domination number of the Cartesian product of graphs is also determined, and graphs that attain it are characterized. Finally, as an application of these results, we determine exact broadcast domination numbers of Hamming graphs and Cartesian products of cycles.

The semigirth \(\gamma\) of a digraph \(D\) is a parameter related to the number of shortest paths in \(D\). In particular, if \(G\) is a graph, the semigirth of the associated symmetric digraph \(G^*\) is \(\ell(G^*) = \lfloor {g(G) – 1}/{2} \rfloor\), where \(g(G)\) is the girth of the graph \(G\). In this paper, some bounds for the minimum number of vertices of a \(k\)-regular digraph \(D\) having girth \(g\) and semigirth \(\ell\), denoted by \(n(k, g; \ell)\), are obtained. Moreover, we construct a family of digraphs which achieve the lower bound for some particular values of the parameters.