Let $\mathrm{\Gamma }$ be a finite group and let $\mathrm{\Delta }$ be a generating set for $\mathrm{\Gamma }$. A Cayley map is an orientable 2-cell imbedding of the Cayley graph $G_{\mathrm{\Delta }}(\mathrm{\Gamma })$ such that the rotation of arcs emanating from each vertex is determined by a unique cyclic permutation of generators and their inverses. A probability model for the set of all Cayley maps for a fixed group and generating set, where the distribution is uniform. We focus on certain finite abelian groups with generating set chosen as the standard basis. A lower bound is provided for the probability that a Cayley map for such a group and generating set is symmetrical.

A graph is asymmetric if the automorphism group of its set of vertices is trivial. A graph is called non-asymmetric if and only if it is not asymmetric. A graph $G$ is minimally non-asymmetric if $G$ is non-asymmetric but $G–e$ is asymmetric for any edge $e$ contained in $G$.

Given a finite set $V$ (of elements called varieties) and integers $k$, $r$, and $\lambda$, a balanced incomplete block design (BIBD) is a family of $k$-element subsets of $V$, called blocks, such that any element is contained in $r$ blocks and any pair of distinct varieties $u$ and $w$ is contained in exactly $\lambda$ blocks.

In this paper, we give examples of minimally non-asymmetric graphs constructed from balanced incomplete block designs.

There is a special case of a generalized Clifford algebra, known as a Clifford graph algebra, which is useful for studying a simple graph $G_n$, with $n$ vertices. We will discuss how this algebra $GA(G_n)$ can represent $G_n$, and prove that it exists in general by defining it as an appropriate sub-algebra of a classical Clifford algebra. We will then refine this process of “construction by inclusion” for the path graph $P_n$, and the complete star graph $K_{1,n}$, by choosing from a parent classical Clifford algebra as many bi-vectors as possible for the generators which define $GA(P_n)$ and $GA(K_{1,n})$.

Elements of the Riordan group $\mathcal{R}$ over a field $\mathbb{F}$ of characteristic zero are infinite lower triangular matrices which are defined in terms of pairs of formal power series. We wish to bring to the forefront, as a tool in the theory of Riordan groups, the use of multiplicative roots $a(x{)}^{\frac{1}{n}}$ of elements $a(x)$ in the ring of formal power series over $\mathbb{F}$. Using roots, we give a Normal Form for non-constant formal power series, we prove a surprisingly simple Composition-Cancellation Theorem and apply this to show that, for a major class of Riordan elements (i.e., for non-constant $g(x)$ and appropriate $F(x)$), only one of the two basic conditions for checking that $(g(x),F(x))$ has order $n$ in the group $\mathcal{R}$ actually needs to be checked. Using all this, our main result is to generalize C. Marshall [6] and prove: Given non-constant $g(x)$ satisfying necessary conditions, there exists a unique $F(x)$, given by an explicit formula, such that $(g(x),F(x))$ is an involution in $\mathcal{R}$. Finally, as examples, we apply this theorem to “aerated” series $h(x)=g(x^r)$ to find the unique $K(x)$ such that $(h(x),K(x))$ is an involution.

A mixed hypergraph is a triple $\mathcal{H}=(X,\mathcal{C},\mathcal{D})$, where $X$ is the vertex set and each of $\mathcal{C}$ and $\mathcal{D}$ is a family of subsets of $X$, the $\mathcal{C}$-edges and $\mathcal{D}$-edges, respectively. A proper $k$-coloring of $\mathcal{H}$ is a mapping such that each $\mathcal{C}$-edge has two vertices with a common color and each $\mathcal{D}$-edge has two vertices with distinct colors. A mixed hypergraph $\mathcal{H}$ is called circular if there exists a host cycle on the vertex set $X$ such that every edge ($\mathcal{C}$- or $\mathcal{D}$-) induces a connected subgraph of this cycle. We propose an algorithm to color the $(3,3)$-uniform, complete, circular, mixed hypergraphs for every value in its feasible set. In doing so, we show: $\chi (\mathcal{H})=2$ and $\overline{\chi }(\mathcal{H})=\frac{n}{2}$ when $n$ is even and $\overline{\chi }(\mathcal{H})=\frac{n-1}{2}$ when $n$ is odd.

For a positive integer $k$, let ${\mathcal{P}}^{\ast }([k])$ be the set of nonempty subsets of the set $[k]=\{1,2,\dots ,k\}$. For a connected graph $G$ of order 3 or more, let $c:E(G)\to {\mathcal{P}}^{\ast }([k])$ be an edge coloring of $G$ where adjacent edges may be colored the same. The induced vertex coloring $c^{\prime }:V(G)\to {\mathcal{P}}^{\ast }([k])$ is defined by $c^{\prime }(v)=\bigcap _{e\in E_v}c(e)$, where $E_v$ is the set of edges incident with $v$. If $c^{\prime }$ is a proper vertex coloring of $G$, then $c$ is called a regal $k$-edge coloring of $G$. The minimum positive integer $k$ for which a graph $G$ has a regal $k$-edge coloring is the regal index $\text{reg}(G)$ of $G$. If $c^{\prime }$ is vertex-distinguishing, then $c$ is a strong regal $k$-edge coloring of $G$. The minimum positive integer $k$ for which $G$ has a strong regal $k$-edge coloring is the strong regal index $\text{sreg}(G)$ of $G$. A brief survey of known results and conjectures on strong regal indexes of graphs is presented. The relationships between the regal index $\text{reg}(G)$ and the chromatic number $\chi (G)$ of a connected graph $G$ are investigated and results and problems on $\text{reg}(G)$ are presented.

One of the routing paradigms on interconnection networks is as follows: given a source node and $m$ destination nodes, find disjoint paths from the source to the destination nodes. If we impose the condition that these paths be the shortest ones, this problem becomes harder and more interesting because such shortest and disjoint paths do not always exist. This problem has been studied previously for $Q_n$, the hypercube of dimension $n$, when $m=n$ and a necessary and sufficient condition has been found for these paths to exist. In this paper, we review the previous work for the hypercube and then consider the problem in the more general case for arbitrary $m$, where $1\le m\le 2^n–1$, in an $n$-cube by designing routing algorithms that always find disjoint and shortest paths for a maximum subset of the destination nodes for which such paths exist. The size of such a set is no more than $n$, the degree of the $Q_n$.

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.

Edge-Nim is a combinatorial game played on finite regular graphs with positive, integrally weighted edges. Two players alternately move from an initialized vertex to an adjacent vertex, decreasing the weight of the incident edge to a strictly non-negative integer as they travel across it. The game ends when no incident edge has a nonzero weight and a player is unable to move, in which case that player loses.

We characterize the winner of Edge-Nim on the complete bipartite graphs $K_{2,n}$ for all positive integers $n$, giving the solution and complete strategy for the player able to win.

Given a graph $G$, we are interested in finding disjoint paths for a given set of distinct pairs of vertices. In 2017, we formally defined a new parameter, the pansophy of $G$, in the context of the disjoint path problem.

In this paper, we investigate the pansophy of two classes of graphs that contain a vertex that we define as the superuser. The superuser of a graph is a vertex that is adjacent to every other vertex. We close with future research directions.

A grid on a cell of a game board attacks all neighboring cells. The domination number counts the minimum number of grids such that each cell of a board is occupied or attacked by a grid.

For square boards (chess boards), the domination number has been determined in a series of papers. Here, we start to consider grids on hexagon boards $B_n$ as parts of the Euclidean tessellation by congruent regular hexagons, where $B_1$ is one hexagon, $B_2$ consists of the three hexagons around one vertex, and $B_n$ for $n\ge 3$ consists of $B_{n-2}$ together with all hexagons having at least one hexagon in common with $B_{n-2}$.

An upper bound is presented for the grid domination number, and exact values are determined by computer for small $n$.

Given a graph $G$, we are interested in finding disjoint paths for a given set of distinct pairs of vertices. In 2017, we formally defined a new parameter, the pansophy of $G$, in the context of the disjoint path problem.

In this paper, we construct a method to determine the pansophy of any complete bipartite graph, and then generalize the method to compute the pansophy of any complete multipartite graph. We close with future research directions.

The \emph{Reconstruction Number} of a graph $G$, denoted $RN(G)$, is the minimum number $k$ such that there exist $k$ vertex-deleted subgraphs of $G$ which determine $G$ up to isomorphism. More precisely, $RN(G)=k$ if and only if there are vertex-deleted subgraphs $G_1,G_2,\dots ,G_k$, such that if $H$ is any graph with vertex-deleted subgraphs $H_1,H_2,\dots ,H_k$, and $G_i\cong H_i$ for $i=1,2,\dots ,k$, then $G\cong H$.

A \emph{unicyclic graph} is a connected graph with exactly one cycle. In this paper, we find reconstruction numbers for various types of unicyclic graphs. With one exception, all unicyclic graphs considered have $RN(G)=3$.

In this work, we introduce the Interval Permutation Segment (IP-SEG) model that naturally generalizes the geometric intersection models of interval and permutation graphs.
We study properties of two graph classes that arise from the IP-SEG model and present a family of forbidden subgraphs for these classes. In addition, we present polynomial algorithms for the following problems on these classes, when the model is given as part of the input.