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 \(\bar{\chi}(\mathcal{H}) = \frac{n}{2}\) when \(n\) is even and \(\bar{\chi}(\mathcal{H}) = \frac{n-1}{2}\) when \(n\) is odd.

For a positive integer \( k \), let \( \mathcal{P}^*([k]) \) be the set of nonempty subsets of the set \( [k] = \{1, 2, \ldots, k\} \). For a connected graph \( G \) of order 3 or more, let \( c: E(G) \to \mathcal{P}^*([k]) \) be an edge coloring of \( G \) where adjacent edges may be colored the same. The induced vertex coloring \( c’: V(G) \to \mathcal{P}^*([k]) \) is defined by \( c'(v) = \bigcap_{e \in E_v} c(e) \), where \( E_v \) is the set of edges incident with \( v \). If \( c’ \) 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’ \) 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 \leq m \leq 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 \((nq^3 – q^3 + nq^2, nq^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, \ldots, 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) \geq n \), then \( cr(G) \geq 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 \leq 16 \), but it remains open for \( n \geq 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 \)).