Strongly regular graphs with parameters $(q^3+2q^2,q^2+q,q,q)$, $(q^3+q^2+q+1,q^2+q,q–1,q+1)$, and $(q^3,q^2+q–2,q–2,q+2)$ are constructed from $k$-arcs in affine planes of order $q$ with $k=q+2,q+1,q$. In addition, strongly regular graphs with parameters $(n{q}^3–q^3+n{q}^2,n{q}^2–q^2+nq–q,2qn–3q,qn–q)$ are constructed from maximal arcs of degree $n$ in affine planes of order $q$. Each of these examples generalizes previously known examples when the affine planes were assumed to be Desarguesian.

The game of Nim is at least centuries old, possibly
originating in China, but noted in the 16th century
in European countries. It consists of several stacks
of tokens, and two players alternate taking one or
more tokens from one of the stacks, and the player
who cannot make a move loses.
The formal and intense study of Nim culminated in
the celebrated Sprague-Grundy Theorem, which is now
one of the centerpieces in the theory of impartial
combinatorial games.
We study a variation on Nim, played on a graph. Graph Nim, for which the theory of
Sprague-Grundy does not provide a clear strategy.
Graph Nim was originally developed at the University
of Colorado Denver.
Graph Nim was first played on graphs of three
vertices. The winning strategy and losing position
of three-vertex Graph Nim have been discovered,
but we will expand the game to four vertices and
develop the winning strategies for four-vertex
Graph Nim.
This work was published as a chapter in the
Master’s Thesis of Trevor Williams [8].

This article discusses Kirchhoff graph uniformity—that all edge vectors in a Kirchhoff graph have the same multiplicity. For a given Kirchhoff graph, an associated digraph is constructed. Based on these graphs, the equivalence of a linear-algebraic condition and a vector graph being Kirchhoff is proven. This condition is then used to show that $2$-connected Kirchhoff graphs are uniform. Other Kirchhoff graphs need not be uniform.

Consider the following two-person game on a graph $G$. The two players start with two color choices only, taking turns coloring any uncolored vertex with the restriction that any coloring must be a proper coloring. A third (or fourth, etc.) color can only be used when forced to maintain a proper coloring. One player, the minimizer, is trying to force the smallest number of colors possible. The other player, the maximizer, is trying to force the largest number of colors possible. This game proper chromatic number, denoted ${\chi }_{(E,g)}(G)$, is the minimum number of colors used when both players play optimally.

The advantage of the game proper chromatic number is that it is comparable to other published game chromatic variants, particularly the game chromatic number II and the game Grundy number.

This paper also considers extensions of the game proper chromatic number through generalized regions of the graph. Let $R=\{R_1,R_2,\dots ,R_t\}$ such that $\bigcup R_i=V(G)$. It is convenient to think of these $R_i$’s as regions of interest in graph $G$. In particular, extensions to closed neighborhoods and open neighborhoods maintaining the restriction that all colorings must be “proper” in the sense that no $R_i$ is monochromatic are considered for some natural classes of graphs.

The minimum number of colors necessary provided each player plays optimally, following the rules established for the game proper chromatic number, is denoted ${\chi }_{(N[v],g)}(G)$ and ${\chi }_{(N(v),g)}(G)$ for the game closed neighborhood proper chromatic number and the game open neighborhood chromatic number, respectively.

A conjecture by Albertson states that if $\chi (G)\ge n$, then $cr(G)\ge cr(K_n)$, where $\chi (G)$ is the chromatic number of $G$ and $cr(G)$ is the crossing number of $G$. This conjecture is true for $n\le 16$, but it remains open for $n\ge 17$.

In this paper, we consider the statements corresponding to this conjecture where the crossing number of $G$ is replaced with:
– the genus $\gamma (G)$ (the minimum genus of the orientable surface on which $G$ is embeddable),
– the skewness $\mu (G)$ (the minimum number of edges whose removal makes $G$ planar), and
– the thickness $\theta (G)$ (the minimum number of planar subgraphs of $G$ whose union is $G$).

In 2017, Hedetniemi asked the question: “For which graphs $G$ does the indexed family $\{N_G(v)\mid v\in V(G)\}$ of open neighborhoods have a system of distinct representatives?” In [1], we answered that question. Now, we move on to other special set families in graphs and examine whether they do or do not have a system of distinct representatives.

We give necessary and sufficient conditions for two matroids on the same ground set to be the upper and lower matroids of a $\mathrm{\Delta }$-matroid.

Let $D$ be a digraph on $n$ vertices. A cycle $C$ in $D$ is said to be 1-extendable if there exists a cycle $C^{\prime }$ in $D$ such that the vertex set of $C^{\prime }$ contains the vertex set of $C$ and $C^{\prime }$ contains exactly one additional vertex. A digraph is 1-cycle-extendable if every non-Hamiltonian cycle is 1-extendable.

A cycle $C$ in $D$ is said to be 2-extendable if there exists a cycle $C^{\prime }$ in $D$ such that the vertex set of $C^{\prime }$ contains the vertex set of $C$ and $C^{\prime }$ contains exactly two additional vertices. A digraph is 2-cycle-extendable if every cycle on at most $n-2$ vertices is 2-extendable.

A digraph is 1,2-cycle-extendable if every non-Hamiltonian cycle is either 1-extendable or 2-extendable. It has been previously shown that not all strong tournaments (orientations of a complete undirected graph) are 1-extendable, but are 2-extendable. The structure of all non 1-extendable tournaments is shown as a type of block Kronecker product of 1-extendable subtournaments.

For a toroidal graph $G=(V,E)$ embedded in the torus, let $\mathcal{F}(G)$ denote the set of faces of $G$. Then, $G$ is called a $C_n$-face-magic torus graph if there exists a bijection $f:V(G)\to \{1,2,\dots ,|V(G)|\}$ such that for any $F\in \mathcal{F}(G)$ with $F\cong C_n$, the sum of all the vertex labelings along $C_n$ is a constant $S$.

Let $x_v=f(v)$ for all $v\in V(G)$. We call $\{x_v:v\in V(G)\}$ a $C_n$-face magic torus labeling on $G$.

We say that a $C_4$-face-magic torus labeling $\{x_{i,j}\}$ on $C_{2n}\times C_{2n}$ is antipodal balanced if $x_{i,j}+x_{i+n,j+n}=\frac{1}{2}S$ for all $(i,j)\in V(C_{2n}\times C_{2n})$.

We determine all antipodal balanced $C_4$-face-magic torus labelings on $C_4\times C_4$ up to symmetries on a torus.

Steinhaus graphs are a small (there are $2^{n-1}$ of them on $n$ vertices) but interesting family of graphs. They have been studied for over forty years, and it has been shown that almost all graphs have certain properties if and only if almost all Steinhaus graphs have these properties.

In this paper, we find and count all the complements of Steinhaus graphs that are claw-free.