In \(1973\), Harary and Palmer posed the problem of enumeration of labeled graphs on \(n \geq 1\) unisolated vertices and \(l \geq 0\) edges. In \(1997\), Bender et al. obtained a recurrence relation representing the sequence \(A054548\)(OEIS) of labeled graphs on \(n \geq 0\) unisolated vertices containing \(q \geq \frac{n}{2}\) edges. In \(2020\), Bhavale and Waphare obtained a recurrence relation representing the sequence of fundamental basic blocks on \(n \geq 0\) comparable reducible elements, having nullity \(l \geq \lfloor \frac{n+1}{2} \rfloor\). In this paper, we prove the equivalence of these two sequences. We also provide an edge labeling for a given vertex labeled finite simple graph.

Let \(G\) be a graph with vertex set \(V\) and edge set \(E\) such that every edge \(e\in E\) belongs to at least one copy of a given subgraph \(H\) of \(G\). A bijection \(f:V\cup E\to \{1,2,\dots,|V|+|E|\}\) is called an \(H\)-supermagic labeling if the sum of labels of all vertices and edges of every copy of \(H\) is equal to the same number \(\mu\) and the vertices are labeled with the first \(|V|\) integers. A \(p\)-calendula graph \(Cal_{m,p[n]}\) consists of a cycle \(C_m\) with \(p\) copies of \(C_n\) amalgamated to each edge of \(C_m\). We generalize a previous result by Pradipta and Salman on 1-calendula graphs by providing \(C_n\)-supermagic labelings of \(Cal_{m,p[n]}\) for all \(m,n\geq3, p\geq 1\), and \(m\neq n\). The case of \(m=n, \ p>1\) remains open.

In this note, we present sufficient conditions involving the independence number, the minimum degree, and the maximum degree for some Hamiltonian properties of a graph.

Recently, it was shown that the Gallai-Ramsey number satisfies \(gr(F_{3,2}, K_3, K_3)=31\), where \(F_{3,2}\) is the generalized fan \(F_{3,2}:=K_1+2K_3\). In this paper, we show that the star-critical Gallai-Ramsey number satisfies \(gr_*(F_{3,2}, K_3, K_3)=27\). We also prove that the critical colorings for \(r_*(K_3, K_3)\), \(gr(F_{3,2},K_3,K_3)\), and \(gr_*(F_{3,2},K_3,K_3)\) are unique.

Richard Rado’s work in Ramsey Theory established conditions under which monochromatic solutions to a linear system must occur. In this paper, we find exact values for a linear system involving the equation \(x_1 + x_2 + c = x_0\) and two colors: Let \(c\) and \(k\) be integers with \(-1 \leq c \leq k\). Then the 2-color Rado number for the system \[\begin{array}{lcl} x_1 + x_2 + c &=& x_0, \\ y_1 + y_2 + k &=& y_0, \end{array}\] is infinite if \(c\) and \(k\) have opposite parity, and has a value of \(4k+5\) if \(c\) and \(k\) have the same parity. We also extend this to the continuous result where we color the real numbers.

In this article, we begin to investigate prime labelings of the zero-divisor graph of a commutative ring. A graph \(G\) with \(n\) vertices admits a prime labeling if the vertices can be labeled using distinct positive integers less than or equal to \(n\) such that any two adjacent vertices have labels which are relatively prime. We are able to construct several infinite families of commutative rings which will have prime labelings for their zero-divisor graphs. We also find infinite families of commutative rings which do not have prime labelings for their zero-divisor graphs. We then continue the process of determining which commutative rings will have prime labelings for their zero-divisor graphs by resolving the question for all rings with 14 or fewer vertices in their zero-divisor graph. We conclude with several unresolved questions that could be interesting to pursue further.

Some methods of constructions of square tactical decomposable regular group divisible designs are described. These designs are useful in threshold schemes. An L_2 design is also identified as square tactical decomposable. This completes spectrum of the solutions of entire L_2 designs listed in Clatworthy [2] using matrix approaches.

Let \(G\) be a loopless connected graph. A graph \(G\) is reduced if it contains no collapsible subgraph. Catlin (posted by Chen and Lai [9]) conjectured that every connected reduced graph is either 2-colorable or 3-colorable. A weaker conjecture states that the independence number of a connected reduced graph \(G\) is at least one-third of its number of vertices. In this paper, we establish a lower bound on the independence number in reduced graphs. As an application, we examine the independence number conjecture for reduced graphs with a given upper bound on the number of vertices. Also, we investigate the chromatic number of reduced planar graphs under given conditions.

Graph pebbling is a network optimization method modeling the movement of resources in transit. A pebbling move on a connected graph \(G\) removes two pebbles from a vertex, places one on an adjacent vertex, and discards the other, with the loss analogous to packet loss in communication networks. The generalized version, \(t\)-pebbling, defines the \(t\)-pebbling number \(f_t(G)\) as the smallest integer such that, from any distribution of \(f_t(G)\) pebbles, \(t\) pebbles can be moved to any vertex \(v\) via a pebbling sequence. A graph satisfies the \(2t\)-pebbling property if \(2t\) pebbles can be transferred to \(v\) when \(2f_t(G)-q+1\) pebbles are distributed, where \(q\) is the number of occupied vertices. This paper establishes a lower bound for the rooted product of two graphs \(G\) and \(H\), sharp when one factor is a path, complete graph, or star. Further results on pebbling in triangle-free graphs are also obtained, including verification of the \(2t\)-pebbling property for rooted products involving such graphs.

It is known that null graphs are the only (regular) graphs with local antimagic chromatic 1 and 1-regular graphs are the only regular graphs without local antimagic chromatic number. In this paper, we first use matrices of size \((2m+1) \times (2k+1)\) to completely determine the local antimagic chromatic number of the join of null graphs \(O_m\) and 1-regular graphs \((2k+1)P_2\) for all \(k\ge 1, m\ge 2\). We then make use of other matrices of same size to obtain the local antimagic chromatic number of another family of tripartite graphs. Consequently, we obtained infinitely many (possibly disconnected) regular tripartite graphs with local antimagic chromatic number 3.

Let \(2\le k\in\mathbb{Z}\). We say that a total coloring of a \(k\)-regular simple graph via \(k+1\) colors is an efficient total coloring if each color yields an efficient dominating set, where the efficient domination condition applies to the restriction of each color class to the vertex set. We prove that Hamming shells of star transposition graphs and Hamming cubes have efficient total colorings. Also in this work, a focus is set upon the graphs of girths \(2k\) and \(k\). Efficient total colorings of finite connected simple cubic graphs of girth 6 are constructed. These are of two specific types, namely: (a) those whose 6-cycles use just 3 colors with antipodal monochromatic pairs of vertices or edges; (b) those whose 6-cycles do not respect item (a) so they use four colors. An orthogonality property holds for all graphs of type (a). Such orthogonality property allows further edge-half-girth colorings in the corresponding prism graphs.

A radio labeling of a graph \( G \) is a mapping \( f : V(G) \to \{0, 1, 2, \dots\} \) such that \( |f(u)-f(v)| \geq \text{diam}(G) + 1 – d(u,v) \) for every pair of distinct vertices \( u,v \) of \( G \), where \( \text{diam}(G) \) is the diameter of \( G \) and \( d(u,v) \) is the distance between \( u \) and \( v \) in \( G \). The radio number \( \text{rn}(G) \) of \( G \) is the smallest integer \( k \) such that \( G \) admits a radio labeling \( f \) with \( \max\{f(v) : v \in V(G)\} = k \). In this paper, we give a lower bound for the radio number of the Cartesian product of a tree and a complete graph and give two necessary and sufficient conditions for the sharpness of the lower bound. We also give three sufficient conditions for the sharpness of the lower bound. We determine the radio number of the Cartesian product of a level-wise regular tree and a complete graph which attains the lower bound. The radio number of the Cartesian product of a path and a complete graph derived in [B. M. Kim, W. Hwang, and B. C. Song, Radio number for the product of a path and a complete graph, J. Comb. Optim., 30 (2015), 139–149] can be obtained using our results in a short way.

Let \( G \) be a connected graph with \( m \) edges. The density of a nontrivial subgraph \( H \) with \( \omega(H) \) components is \( d(H) = \frac{|E(H)|}{|V(H)| – \omega(H)} \). A graph \( G \) is uniformly dense if for any nontrivial subgraph \( H \) of \( G \), \( d(H) \leq d(G) \). For each cyclic ordering \( o=(e_1, e_2, \dots, e_m) \) of \( E(G) \), let \( h(o) \) be the largest integer \( k \) such that every \( k \) cyclically consecutive elements in \( o \) induce a forest in \( G \); and the largest \( h(o) \), taken among all cyclic orderings of \( G \), is denoted by \( h(G) \). A cyclic ordering \( o \) of \( G \) is a cyclic base ordering if \( h(o) = |V(G)| – \omega(G) \). In [15], Kajitani et al. proved that every connected nontrivial graph with a cyclic base ordering is uniformly dense, and conjectured that every uniformly dense graph has a cyclic base ordering. This motivates the study of \( h(G) \). In this paper, we investigate the value of \( h \) for some families of graphs and determine all connected graphs \( G \) with \( h(G) \leq 2 \).

An open-locating-dominating set of a graph models a detection system for a facility with a possible “intruder” or a multiprocessor network with a possible malfunctioning processor. A “sensor” or “detector” is assumed to be installed at a subset of vertices where each can detect an intruder or a malfunctioning processor in its neighborhood, but not at its own location. We consider a fault-tolerant variant of an open-locating-dominating set called an error-correcting open-locating-dominating set, which can correct a false-positive or a false-negative signal from a detector. In particular, we prove the problem of finding a minimum error-correcting open-locating-dominating set in an arbitrary graph is NP-complete. Additionally, we characterize the existence criteria for an error-correcting open-locating-dominating set in an arbitrary graph. We also consider extremal graphs that require every vertex to be a detector and minimum error-correcting open-locating-dominating sets in infinite grids.

Let \( G = (V, E) \) be a graph with vertex set \( V \) and edge set \( E \). A set \( S \subset V \) is a dominating set if every vertex in \( V – S \) is adjacent to at least one vertex in \( S \), an independent set if no two vertices in \( S \) are adjacent, and a total dominating set if every vertex in \( V \) is adjacent to at least one vertex in \( S \). The domatic number \( \text{dom}(G) \), idomatic number \( \text{idom}(G) \), and total domatic number \( \text{tdom}(G) \), of a graph \( G \) equal the maximum order \( k \) of a partition \( \pi = \{V_1, V_2, \ldots, V_k\} \) of \( V \) into {dominating sets, independent dominating sets, total dominating sets}, respectively. A queens graph \( Q_n \) is a graph defined on the \( n^2 \) squares of an \( n \)-by-\( n \) chessboard, such that two squares are adjacent if and only if a queen on one square can move to the other square in one move, that is, the two squares lie on a common row, column, or diagonal. In this note, we determine the value of these three numbers for \( Q_n \) for the first several values of \( n \). In addition, we introduce the concepts of graphs being \( \gamma \)-domatic, \( i \)-domatic, \( \alpha \)-domatic, \( \Gamma \)-domatic, \( \gamma_t \)-domatic, and \( \Gamma_t \)-domatic.

A Magic Venn Diagram is a magic figure where regions of a Venn diagram are labeled such that the sums of the regional labels of each set are the same. We have developed a backtracking search to count the number of Magic Venn Diagrams. The algorithm could determine the number of Magic Venn Diagrams for all Venn diagrams with four sets. This paper presents the algorithm with its applied heuristics and lists the computational results.

A famous open problem in the field of rendezvous search is to ascertain the rendezvous value of the symmetric rendezvous problem on the line, wherein both agents begin two units apart. We provide a new, Bayesian framework to both create new strategies for the agents to follow and to provide a new interpretation of previously posited strategies.
Additionally, we have developed a method that modifies any strategy, even those with potentially infinite expected meeting time, into a new strategy that is guaranteed to have a finite expected meeting time. This process, combined with using our Bayesian framework to create new strategies, yields an upper bound that is within one percent of the current best upper bound for the symmetric rendezvous value.

The Astronaut Problem is an open problem in the field of rendezvous search. The premise is that two astronauts randomly land on a planet and want to find one another. Research explores what strategies accomplish this in the least expected time.
To investigate this problem, we create a discrete model which takes place on the edges of the Platonic solids. Some baseline assumptions of the model are:

1. The agents can see all of the faces around them.
2. The agents travel along the edges from vertex to vertex and cannot jump.
3. The agents move at a rate of one edge length per unit time.

The 3-dimensional nature of our model makes it different from previous work. We explore multi-step strategies, which are strategies where both agents move randomly for one step, and then follow a pre-determined sequence.

For the cube and octahedron, we are able to prove optimality of the “Left Strategy,” in which the agents move in a random direction for the first step and then turn left. In an effort to find lower expected times, we explore mixed strategies. Mixed strategies incorporate an asymmetric case which, under certain conditions, can result in lower expected times.

Most of the calculations were done using first-step decompositions for Markov chains.

Our research focuses on the winning probability of a novel problem posted on a question-and-answer website. There are \( n \) people in a line at positions \( 1, 2, \ldots, n \). For each round, we randomly select a person at position \( i \), where \( i \) is odd, to leave the line, and shift each person at a position \( j \) such that \( j > i \) to position \( j – 1 \). We continue to select people until there is only one person left, who then becomes the winner.

We are interested in which initial position has the greatest chance to survive, that is, the highest probability to be the last one remaining. Specifically, we have derived recursions to solve for exact values and the formula of the winning probabilities.

We have also considered variations of the problem, where people are grouped into triples, quadruples, etc., and the first person in each group is at the risk of being selected. We will also present various sequences we have discovered while solving for the winning probabilities of the different variations, as well as other possible extensions and related findings concerning this problem.

Our research studies the expected survival time in a novel problem posted on a question-and-answer website. There are \( n \) people in a line at positions \( 1, 2, \ldots, n \). For each round, we randomly select a person at position \( k \), where \( k \) is odd, to leave the line, and shift the person at each position \( i > k \) to position \( i-1 \). We continue to select people until there is only one person left, who then becomes the winner.

We are interested in which initial position has the largest expected number of turns to stay in the line before being selected, which we refer to as “expected survival time.” In this paper, we use a recursive approach to solve for exact values of the expected survival time. We have proved the exact formula of the expected survival time of the first and the last position as well. We will also present our work on the expected survival time of the other positions, \( 2, 3, 4, \ldots \) from an asymptotic perspective.

A set \( S \subseteq V \) is a dominating set of \( G \) if every vertex in \( V – S \) is adjacent to at least one vertex in \( S \). The domination number \( \gamma(G) \) of \( G \) equals the minimum cardinality of a dominating set \( S \) in \( G \); we say that such a set \( S \) is a \( \gamma \)-set.

A generalization of this is partial domination, which was introduced in 2017 by Case, Hedetniemi, Laskar, and Lipman. In \emph{partial domination}, a set \( S \) is a \( p \)-dominating set if it dominates a proportion \( p \) of the vertices in \( V \). The \( p \)-domination number \( \gamma_p(G) \) is the minimum cardinality of a \( p \)-dominating set in \( G \).

In this paper, we investigate further properties of partial dominating sets, particularly ones related to graph products and locating partial dominating sets. We also introduce the concept of a \( p \)-influencing set as the union of all \( p \)-dominating sets for a fixed \( p \) and investigate some of its properties.

For bipartite graphs \( F \) and \( H \) and a positive integer \( s \), the \( s \)-bipartite Ramsey number \( BR_s(F,H) \) of \( F \) and \( H \) is the smallest integer \( t \) with \( t \geq s \) such that every red-blue coloring of \( K_{s,t} \) results in a red \( F \) or a blue \( H \). We evaluate this number for all positive integers \( s \) when \( F \) and \( H \) are both stars, are both matchings, or one is a star and the other is a matching, as well as when \( F = H \) is an arbitrary double star.

In a graph \( G \), the Steiner distance \( d(S) \) of the vertex subset \( S \subseteq V(G) \) is the minimum size among all connected subgraphs whose vertex sets contain \( S \). The Steiner \( k \)-diameter of a connected graph \( G \) is the maximum \( d(S) \) among all \( k \)-element vertex subsets \( S \subseteq V(G) \).

In this paper, we examine the Steiner \( k \)-diameter for large \( k \) and then discuss the applications of the results.

A set of vertices, \( S \), in a digraph \( D \), is split dominating provided it is:

1. dominating and
2. \( D[V(D) \setminus S] \) is either trivial or has a lower level of connection than \( D \).

In this paper, we consider split dominating sets in strongly connected tournaments. The split domination number of a strongly connected tournament \( T \), denoted by \( \gamma_s(T) \), is the minimum cardinality of a split dominating set for that tournament.

The authors previously gave a tight lower bound for \( \gamma_s(T) \) when \( T \) is regular. In this paper, we show that when \( T \) is a nearly regular \( 2k \)-tournament, then \( \gamma_s(T) \geq \lceil \frac{2k}{3} \rceil \) and this bound is tight.

Redrawing lines for redistricting plans that represent U.S. congressional districts is a tricky business. There are many laws that dictate how lines can and cannot be drawn, such as contiguity. In fact, building all redistricting plans for a single U.S. state is an intractable problem. Researchers have turned to heuristics in order to analyze current redistricting plans. Many of these heuristics (e.g. local search heuristics and Markov chain Monte Carlo algorithms) used by researchers form new congressional districts by switching the smaller pieces (e.g. precincts or census blocks) that make up congressional districts from one congressional district to another.
In this paper, we discuss the various natural definitions involved in satisfying rules for contiguity and simply connectedness of precincts or census blocks and how these relate to contiguity and simply connectedness of congressional districts. We also propose and analyze several constructions to alleviate violations of contiguity and simply connectedness in precincts and census blocks. Finally, we develop efficient algorithms that allow practitioners to assess redistricting plans using local search heuristics or Markov chain Monte Carlo algorithms efficiently.

A set \( S \subseteq V \) is \( \alpha \)-dominating if for all \( v \in V – S \), \( |N(v) \cap S| \geq \alpha |N(v)| \). The \( \alpha \)-domination number of \( G \) equals the minimum cardinality of an \( \alpha \)-dominating set \( S \) in \( G \). Since being introduced by Dunbar et al. in 2000, \( \alpha \)-domination has been studied for various graphs and a variety of bounds have been developed.

In this paper, we propose a new parameter derived by flipping the inequality in the definition of \( \alpha \)-domination. We say a set \( S \subset V \) is a \( \beta \)-packing set of a graph \( G \) if \( S \) is a proper, maximal set having the property that for all vertices \( v \in V – S \), \( |N(v) \cap S| \leq \beta |N(v)| \) for some \( 0 < \beta \leq 1 \). The \( \beta \)-\emph{packing number} of \( G \), denoted \( \beta\text{-pack}(G) \), equals the maximum cardinality of a \( \beta \)-packing set in \( G \).

In this research, we determine \( \beta\text{-pack}(G) \) for several classes of graphs, and we explore some properties of \( \beta \)-packing sets.

A perfect matching of a graph is a subset of edges in the graph such that each vertex is contained in exactly one edge. We study the number of perfect matchings of a given graph. In particular, we are interested in the power of two that divides this number. A new type of vertex set, called a channel, is considered, whose presence is associated with powers of two in the perfect matching count. This provides a method for determining lower bounds on such powers. Algebraic and involutive proofs are given for these results, and methods for channel identification are provided. We specialize to perfect matchings on subgraphs of the square lattice, which are identified with domino tilings of the plane, and apply channels to some conjectures by Pachter.

A dominating set of a graph \( G \) is a set of vertices \( D \) such that for all \( \nu \in V(G) \), either \( \nu \in D \) or \( [\nu,d] \in E(G) \) for some \( d \in D \). The cardinality-redundance of a vertex set \( S \), \( CR(S) \), is the number of vertices \( x \in V(G) \) such that \( |N[x] \cap S| \geq 2 \). The cardinality-redundance of \( G \) is the minimum of \( CR(S) \) taken over all dominating sets \( S \). A set of vertices \( S \) such that \( CR(S) = CR(G) \) is a \( \gamma_{CR} \)-set, and the size of a minimum \( \gamma_{CR} \)-set is denoted \( \gamma_{CR}(G) \).

Here, we are concerned with extremal problems concerning cardinality-redundance. We give the maximum number of edges in a graph with a given number of vertices and given cardinality-redundance. In the cases that \( CR(G) = 0 \) or \( 1 \), we give the minimum and maximum number of edges of graphs when \( \gamma_{CR}(G) \) is fixed, and when \( CR(G) = 2 \), we give the maximum number of edges of graphs where \( \gamma_{CR}(G) \) is fixed. We give the minimum and maximum values of \( \gamma_{CR}(G) \) when the number of edges are fixed and \( CR(G) = 0, 1 \), and we give the maximum values of \( \gamma_{CR}(G) \) when the number of edges are fixed and \( CR(G) = 2 \).

It is known that for a maximal planar graph \( G \) with order \( n \geq 4 \), the independence number satisfies \( \frac{n}{4} \leq \alpha(G) \leq \frac{2n-4}{3} \). We show that the lower bound is sharp and characterize the extremal graphs for \( n \leq 12 \). For the upper bound, we characterize the extremal graphs of all orders.

The independence number \( \alpha(G) \) of a graph \( G \) is the size of the largest independent set. This parameter is difficult to determine in general, but can be bounded on various graph classes. This paper considers planar and maximal planar graphs.

Constraint Programming (CP) is a method used to model and solve complex combinatorial problems. An alternative to Integer Programming for solving large-scale industrial problems, it is, under some circumstances, more efficient than IP, but its strength lies mainly in the use of predicates to model problems. This paper presents the at-least-\( m \)-different predicate and provides a class of facet-defining inequalities of the convex hull of integer solutions. This predicate bounds the number of values that variables in a set may receive. The paper also presents a polynomial-time separation algorithm to be used in the context of a branch-and-bound optimization approach.

Let \( N_2DL(v) \) denote the set of degrees of vertices at distance \( 2 \) from \( v \). The \( 2 \)-neighborhood degree list of a graph is a listing of \( N_2DL(v) \) for every vertex \( v \). A degree restricted \( 2 \)-switch on edges \( v_1v_2 \) and \( w_1w_2 \), where \( \deg(v_1) = \deg(w_1) \) and \( \deg(v_2) = \deg(w_2) \), is the replacement of a pair of edges \( v_1v_2 \) and \( w_1w_2 \) by the edges \( v_1w_2 \) and \( v_2w_1 \), given that \( v_1w_2 \) and \( v_2w_1 \) did not appear in the graph originally. Let \( G \) and \( H \) be two graphs of diameter \( 2 \) on the same vertex set. We prove that \( G \) and \( H \) have the same \( 2 \)-neighborhood degree list if and only if \( G \) can be transformed into \( H \) by a sequence of degree restricted \( 2 \)-switches.

Let \( \Gamma \) be a finite group and let \( \Delta \) be a generating set for \( \Gamma \). A Cayley map is an orientable 2-cell imbedding of the Cayley graph \( G_\Delta(\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 \(\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 \)).

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 \( \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’ \) in \( D \) such that the vertex set of \( C’ \) contains the vertex set of \( C \) and \( C’ \) 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’ \) in \( D \) such that the vertex set of \( C’ \) contains the vertex set of \( C \) and \( C’ \) 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) \rightarrow \{1, 2, \ldots, |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 \geq 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, \ldots, G_k \), such that if \( H \) is any graph with vertex-deleted subgraphs \( H_1, H_2, \ldots, H_k \), and \( G_i \cong H_i \) for \( i = 1, 2, \ldots, 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.

Let \( S_n \) be the random walk on \( (0, 1) \). The \( S_n \) have been the subject of intense study; their definition is immediately intuitive. Nevertheless, they are quite intentionally disorderly, and this disorder is mirrored by the fact that, pointwise, \( \left( \frac{S_n}{\sqrt{n}} \mid n \in \mathbb{N}^+ \right) \) behaves quite badly.

In this paper, we provide our results on the fine structure of the random walk that give insight into this behavior.

We utilize the flexible tile model presented in [13] to design self-assembling DNA structures from a graph theory perspective. These tiles represent branched junction molecules whose arms are double strands of DNA.

We consider \( 2 \times n \) triangular lattice graphs \( G_n \), where \( n \) represents the number of triangles. Given a target graph \( G_n \), we determine the minimum number of tile and bond-edge types needed in order to create \( G_n \) as a complete self-assembled complex in three different scenarios. Each scenario corresponds to a distinct level of laboratory constraint.

In the first scenario, graphs of a smaller size than \( G_n \) are allowed. In the second scenario, non-isomorphic graphs of the same size as \( G_n \) are allowed, but not graphs of smaller size. In the third scenario, only graphs isomorphic or larger in size to the target graph are allowed.

We provide optimal tile sets for all \( 2 \times n \) triangular lattice graphs \( G_n \) in Scenario 1 and Scenario 3. We also include some small examples in Scenario 2.

An upper bound on the energy of graphs is obtained using the spectral moments of the eigenvalues of the adjacency matrix associated with the graph, utilizing the method of Lagrange multipliers and properties of cubic equations

A polyhex is a set of hexagons of the Euclidean tessellation of the plane by congruent regular hexagons. Then, a polyhex graph has the vertex points of the hexagons as its vertices and the sides of the hexagons as its edges. A rectilinear drawing of a graph in the plane uses straight line segments for the edges. Partial results are given for the maximum number of crossings over all rectilinear drawings of a polyhex graph

Distinctive power of the alliance polynomial has been studied in previous works. For instance, it has been proved that the empty, path, cycle, complete, complete without one edge, and star graphs are characterized by its alliance polynomial. Moreover, it has been proved that the family of alliance polynomials of regular graphs with small degree is a very
special one, since it does not contain alliance polynomials of graphs other than regular graphs with the same degree. In this work, we prove that the alliance polynomial also
determines the wheel graphs.

An ordered tree, also known as a plane tree or a planar tree, is defined recursively as having a root and an ordered set of subtrees. A \(3\)-zebra tree is an ordered tree where all edges connected to the root (called height \( 1 \)) are tricolored, as are all edges at odd height. The edges at even height are all black as usual.

In this paper, we show that the number of \(3\)-zebra trees with \( n \) edges is equal to the number of Schröder paths with bicolored level steps.

A split graph is a graph whose vertices can be partitioned into a clique and an independent set. Most results in spectral graph theory do not address multigraph concerns. Exceptions are [2] and [4], but these papers present results involving a special class of underlying split graphs, threshold graphs, in which all pairs of nodes exhibit neighborhood nesting, and all multiple edges are confined to the clique.

We present formulas for the eigenvalues of some infinite families of regular split multigraphs in which all multiple edges occur between the clique nodes and cone nodes, with multiplicity of multiple edges \( \mu > 1 \) fixed, and which have integer eigenvalues for the adjacency, Laplacian, and signless Laplacian matrices.

A rigid vertex is a vertex with a prescribed cyclic order of its incident edges. An embedding of a rigid vertex graph preserves such a cyclic order in the surface at every vertex. A cellular embedding of a graph has the complementary regions homeomorphic to open disks.

The genus range of a \( 4 \)-regular rigid vertex graph \( \Gamma \) is the set of genera of closed surfaces that \( \Gamma \) can be cellularly embedded into. Inspired by models of DNA rearrangements, we study the change in the genus range of a graph \( \Gamma \) after the insertion of subgraph structures that correspond to intertwining two edges. We show that such insertions can increase the genus at most by \( 2 \) and decrease by at most \( 1 \), regardless of the number of new vertices inserted.

The hypercube cut number \( S(d) \) is the minimum number of hyperplanes in the \( d \)-dimensional Euclidean space \( \mathbb{R}^d \) that slice all the edges of the \( d \)-cube. The problem was originally posed by P. O’Neil in 1971. B. Grünbaum, V. Klee, M. Saks, and Z. Füredi have raised the problem in various contexts.

The identity \( S(d) = d \) has been well-known for \( d \leq 4 \) since 1986. However, it was only until the year 2000 that Sohler and Ziegler obtained a computational proof for \( S(5) = 5 \). Nevertheless, finding a short proof for the problem, independent of computer computations, remains a challenging task.

We present a short proof for the result presented by Emamy-Uribe-Tomassini in Hypercube 2002 based on Tomassini’s Thesis. The proof here is substantially shorter than the original proof of 60 pages.

Percolation models are infinite random graph models which have applications to phase transitions and critical phenomena. In the site percolation model, each vertex in an infinite graph \( G \) is retained independently with probability \( p \) and deleted otherwise. The percolation threshold is the critical probability \( p_c(G) \) such that if \( p > p_c(G) \), there is positive probability that the random subgraph induced by the retained vertices has an infinite connected component, while the probability that all of its components are finite is one if \( p < p_c(G) \).

There are few lattice graphs for which the site percolation threshold is exactly known, and rigorous bounds for unsolved lattices are very imprecise. The substitution method for computing bounds for the more common class of bond percolation models must be modified to apply to site models. Some modifications will be illustrated with an application to the \( (4,8^2) \) Archimedean lattice, which is a vertex-transitive tiling of the plane by squares and regular octagons. An improved upper bound, \( p_c^{site}(4,8^2) < 0.785661 \), is obtained.

In a finite projective plane \( \text{PG}(2, q) \), a set of \( k \) points is called a \( (k, n) \)-arc if the following two properties hold:
1. Every line intersects it in at most \( n \) points.
2. There exists a line which intersects it in exactly \( n \) points.

We are interested in determining, for each \( q \) and each \( n \), the largest value of \( k \) for which a \( (k, n) \)-arc exists in \( \text{PG}(2, q) \). If possible, we would like to classify those arcs up to isomorphism. We look at the problem for \( q = 11 \).

A cyclic triple, \( (a, b, c) \), is defined to be the set \( \{(a, b), (b, c), (c, a)\} \) of ordered pairs. A Mendelsohn triple system of order \( v \), or MTS\( (v) \), is a pair \( (M, \beta) \), where \( M \) is a set of \( v \) points and \( \beta \) is a collection of cyclic triples, each containing pairwise distinct points of \( M \) such that every ordered pair of distinct points of \( M \) exists in exactly one cyclic triple of \( \beta \). An antiautomorphism of a Mendelsohn triple system \( (M, \beta) \) is a permutation of \( M \) which maps \( \beta \) to \( \beta^{-1} \), where \( \beta^{-1} = \{(c, b, a) \mid (a, b, c) \in \beta\} \). Necessary conditions for the existence of an MTS\( (v) \) admitting an antiautomorphism consisting of two cycles of lengths \( M \) and \( N \), where \( 1 < M \leq N \), have been shown, and for the cases of \( N = M \) and \( N = 2M \), sufficiency has been shown. We show sufficiency for the cases in which \( M = 13 \) and \( N = 78, 390, \) and \( 702 \).

The study of the generalized Fermat variety

\[
\phi_j = \frac{x^j + y^j + z^j + (x+y+z)^j}{(x+y)(x+z)(y+z)}
\]

defined over a finite field \( L = \mathbb{F}_q \), where \( q = 2^n \) for some positive integer \( n \), plays an important role in the study of (APN) functions and exceptional APN functions. This study arose after a characterization by Rodier that relates these functions with the number of rational points of \( \phi_j = (x,y,z) \). The most studied cases are when \( j = 2^k + 1 \) and \( j = 2^{2k} – 2^{k} + 1 \), the Gold and Kasami-Welch numbers. In this article, we make a claim about the decomposition of \( \phi_j \) into absolutely irreducible components. If these components intersect transversally at a particular point, then the corresponding Kasami-Welch polynomial is absolutely irreducible. This implies that the function is not exceptional APN, thus helping us make progress on the stated conjecture.

For \( n \geq 1 \), let \( a_n \) count the number of strings \( s_1 s_2 s_3 \ldots s_n \), where
(i) \( s_1 = 0 \);
(ii) \( s_i \in \{0, 1, 2\} \) for \( 2 \leq i \leq n \);
(iii) \( |s_i – s_{i-1}| \leq 1 \) for \( 2 \leq i \leq n \).

Then \( a_1 = 1 \), \( a_2 = 2 \), \( a_3 = 5 \), \( a_4 = 12 \), and \( a_5 = 29 \).

In general, for \( n \geq 3 \), \( a_n = 2a_{n-1} + a_{n-2} \), and \( a_n \) equals \( P_n \), the \( n \)th \emph{Pell} number.

For these \( P_n \) strings of length \( n \), we count
(i) The number of occurrences of each symbol \( 0, 1, 2 \);
(ii) The number of times each symbol \( 0, 1, 2 \) occurs in an even or odd position;
(iii) The number of levels, rises, and descents within the strings;
(iv) The number of runs that occur within the strings;
(v) The sum of all strings considered as base \( 3 \) integers;
(vi) The number of inversions and coinversions within the strings; and
(vii) The sum of the major indices for the strings.

A family of graphs, called Generalized Johnson graphs, provides an abstraction of both Kneser and Johnson graphs.
Given the symmetric nature of Generalized Johnson graphs, we provide various decompositions of these graphs and demonstrate non-trivial instances of the impossibility of decomposing such graphs into triples.