Skip to main content
Top

2024 | Book

Combinatorics, Graph Theory and Computing

SEICCGTC 2021, Boca Raton, USA, March 8–12

insite
SEARCH

About this book

This proceedings volume convenes selected, revised papers presented at the 52nd Southeastern International Conference on Combinatorics, Graph Theory and Computing (SEICCGTC 2021), virtually held at Florida Atlantic University in Boca Raton, USA, on March 8-12, 2021. As has been a tradition since its inception in 1970, this edition once more brought together mathematicians, practitioners, and scientists around novel findings in combinatorics, graph theory and computing, and their interactions.
The lectures and works presented at the Conference have proven to be of great interest to other scientists and analysts employing these mathematical sciences in their professional activities in business, industry, and government. Such an environment promotes a better understanding of the roles of modern applied mathematics, combinatorics, and computer science. Many works have demonstrated that disciplines have increasingly contributed to each other. With this series of Conferences, the gaps between the fields tend to decrease even further.
This volume is of particular interest for the community of pure and applied mathematicians in academia, industry, and government, working in combinatorics and graph theory, as well as related areas of computer science and the interactions among these fields. Its findings can also benefit a general audience of practitioners and students from related fields.

Table of Contents

Frontmatter
The es-splitting Operation for Matroids Representable Over Prime Fields GF(p)

The es-splitting operation for binary matroids is a natural generalization of Slater’s n-line splitting operation on graphs. The present paper extends the es-splitting operation to the matroids representable over the field GF(p), called the p-matoids. We characterize circuits, and bases of the resulting matroid in terms of the circuits, and the bases of the original matroid, respectively. It is proved that the es-splitting operation preserves the connectivity of the p-matoids. A Sufficient condition to obtain a 3-connected p-matroid from a 3-connected p-matroid using the es-splitting operation is also provided. In the last section, we obtain a sufficient condition to produce an Eulerian p-matroid from an Eulerian p-matroid using es-splitting operation.

Prashant Malavadkar, Sachin Gunjal, Uday Jagadale, M. M. Shikare, B. N. Waphare
The Existence Problem for Strong Complete Mappings of Finite Groups

The Cayley table M and the normal multiplication table N of a finite group G are Latin squares. There exists a Latin square orthogonal to both M and N if and only if G admits strong complete mappings. A natural question to ask is, which finite groups admit strong complete mappings? We will summarize work done on the existence problem for strong complete mappings of finite groups. We will also establish new classes of strongly admissible 2-groups. We will also give theoretical proofs of the strong admissibility of some groups of order 16, whose strong admissibility has only been proved via computer searches.

Anthony B. Evans
Differences of Functions with the Same Value Multiset

In a recent article, Ullman and Velleman studied functions a from an abelian group G to itself that can be expressed as a difference of two bijections b, c from G to itself. In this work we relax the condition that b and c are bijections and instead study functions that can be expressed as the difference of two functions with the same value multiset. We construct all possible functions b, c with same value multiset, such that $$a = b - c$$ a = b - c . As a consequence, we obtain a stronger version of Hall’s theorem, which gives a description of b and c in terms of a. We conclude by presenting further directions and questions that relate this new approach to applications of Hall’s theorem.

Dylan Cruz, Andrés Ramos, Ivelisse Rubio
Mixed-Level Covering, Locating, and Detecting Arrays via Cyclotomy

For a finite field of order q, and v a divisor of $$q-1$$ q - 1 , additive translates of a cyclotomic vector yield a $$q \times q$$ q × q cyclotomic array on v symbols. For every positive integer t, for certain q sufficiently large with respect to v, such a cyclotomic array is always a covering array of strength t. Asymptotically such arrays have far too many rows to be competitive with certain other covering array constructions. Nevertheless, for small values of t, this cyclotomic method produces smallest known covering arrays for numerous parameters suitable for practical application. This paper extends these ideas and shows that cyclotomy can produce covering arrays of higher index, and locating and detecting arrays with large separation. Computational results also demonstrate that certain cyclotomic arrays for the same order q but different values of v can be juxtaposed to produce mixed-level covering, locating, and detecting arrays.

Yasmeen Akhtar, Charles J. Colbourn, Violet R. Syrotiuk
Resolutions for an Infinite Family of Bose Triple Systems

A classical construction of Bose produces a Steiner triple system of order 3n from a symmetric, idempotent latin square of order n whenever n is odd. In an application to access-balancing in storage systems, these Bose triple systems play a central role. A natural question arises: For which orders n does there exist a resolvable Bose triple system? In this paper, a resolution of the Bose-averaging triple system of order 3n is determined whenever $$n = 3p$$ n = 3 p and $$p \ge 5$$ p ≥ 5 is prime.

Dylan Lusi, Charles J. Colbourn
Decomposition of the Johnson Graphs into Graph-Pairs of Order 4

A graph-pair of order t is a pair of graphs G and H on t non-isolated vertices for which $$G \cup H \cong K_t$$ G ∪ H ≅ K t for some integer $$t \ge 4$$ t ≥ 4 . The Johnson graph J(v, n) is the graph whose vertices are the n-element subsets of a v-element set, and two vertices are adjacent if the intersection of the corresponding subsets contains $$n-1$$ n - 1 elements. We show necessary and sufficient conditions for J(v, 2) to admit a decomposition into graph-pairs of order 4.

Atif Abueida, Mike Daven
Some New Strongly Regular Graphs from Quadrics

We construct new strongly regular graphs with parameters (85, 20, 3, 5) and (4369, 272, 15, 17). These parameters are the same as those arising from the generalized quadrangle $$\textrm{Q}(4,4^h)$$ Q ( 4 , 4 h ) for $$h=1,2$$ h = 1 , 2 .

Liz Lane-Harvard, Tim Penttila
Nonexistence of a Subfamily of a Family of Edge-Regular Graphs

A simple, non-edgeless, regular graph is said to be edge-regular if the cardinality of the intersection of the neighborhoods of every pair of adjacent vertices is a fixed integer $$\lambda .$$ λ . Edge-regular graphs necessarily have a constant number p of common non-neighbors for every adjacent vertex pair. Much work has been done to determine the extremal edge-regular graphs for the inequality $$n\le 3(\lambda + p)$$ n ≤ 3 ( λ + p ) , as well as the edge-regular graphs satisfying $$n=3(\lambda + p) -2$$ n = 3 ( λ + p ) - 2 with added structural conditions, where n is the number of vertices and $$\lambda > 0$$ λ > 0 . We consider the case where $$ n = 3(\lambda + p) -4$$ n = 3 ( λ + p ) - 4 , with the added condition that the common neighbor set of every pair of adjacent vertices induces $$\frac{\lambda }{2}K_2$$ λ 2 K 2 , a disjoint union of edges.

Robert McNellis, Tabitha Parker, Kenneth Roblee
On a Convex Geometric Connection to Threshold Logic

A convex geometric connection to Threshold Logic will be reviewed. We have presented necessary and sufficient conditions to recognize cut-complexes with 2 or 3 maximal faces from the class of all cubical complexes. This recognition of cut-complexes is closely related to an old proposal on cubical lattices by N. Metropolis and G. C. Rota. They proposed cubical lattices may also be used for synthesis of Boolean functions parallel to the conventional Boolean algebraic methods. The characterization will be applied to recognize several cut-complexes in the 4-dimensional cube. The cut-complexes of the 4-cube are used to define a new poset that happens to be a distributive lattice.

M. R. Emamy-K., Gustavo A. Meléndez Ríos
Multicore Graphs: Characterization and Properties

In this paper we define the multicore graphs, a subclass of chordal graphs that extends the gen core-satellite graphs, defined by Estrada and Benzi (Linear Algebra App. 517:30–52 (2017)) [5]. We prove that the multicore graphs are the $$(P_5,gem,dart)$$ ( P 5 , g e m , d a r t ) -free chordal graphs and we present a characterization of the class which provides a simple linear time recognition algorithm. We also show its interrelation with other subclasses of chordal graphs: the clique-corona graphs and the starlike graphs.

Lilian Markenzon, Newton Paciornik
Cospanning Characterizations of Violator and Co-violator Spaces

Given a finite set E and an operator $$\sigma :2^{E}\longrightarrow 2^{E}$$ σ : 2 E ⟶ 2 E , two subsets $$X,Y\subseteq E$$ X , Y ⊆ E are cospanning if $$\sigma (X)=\sigma (Y)$$ σ ( X ) = σ ( Y ) (Korte, Lovász, Schrader; 1991). We investigate cospanning relations on violator spaces. A notion of a violator space was introduced in (Gärtner, Matoušek, Rüst, Škovroňby; 2008) as a combinatorial framework that encompasses linear programming and other geometric optimization problems. Violator spaces are defined by violator operators. We introduce co-violator spaces based on contracting operators known also as choice functions. Let $$\alpha ,\beta :2^{E}\longrightarrow 2^{E}$$ α , β : 2 E ⟶ 2 E be a violator operator and a co-violator operator, respectively. Cospanning characterizations of violator spaces allow us to obtain some new properties of violator operators and co-violator operators, emphasizing their interconnections. In particular, we show that uniquely generated violator spaces satisfy so-called Krein-Milman properties, i.e., $$\alpha (\beta \left( X\right) )=\alpha (X)$$ α ( β X ) = α ( X ) and $$\beta \left( \alpha \left( X\right) \right) =\beta \left( X\right) $$ β α X = β X for every $$X\subseteq E$$ X ⊆ E .

Yulia Kempner, Vadim E. Levit
(2, 3)-Cordial Trees and Paths

Recently L. B. Beasley introduced (2, 3)-cordial labelings of directed graphs in [1]. He conjectured that every orientation of a path of length at least five is (2, 3)-cordial, and that every tree of max degree $$n =3$$ n = 3 has a cordial orientation. In this paper we formally define (2, 3)-cordiality from the viewpoint of quasigroup cordiality. We show both conjectures to be false, discuss the (2, 3)-cordiality of orientations of the Petersen graph, and establish an upper bound for the number of edges a graph can have and still be (2, 3)-orientable.

Manuel Santana, Jonathan Mousley, Dave Brown, LeRoy B. Beasley
(2, 3)-Cordial Oriented Hypercubes

In this article we investigate the existence of (2, 3)-cordial labelings of oriented hypercubes. In this investigation, we determine that there exists a (2, 3)-cordial oriented hypercube for any dimension divisible by 3. Next, we provide examples of (2, 3)-cordial oriented hypercubes of dimension not divisible by 3 and state a conjecture on existence for dimension $$3k + 1$$ 3 k + 1 . We close by presenting the only 3D oriented hypercubes up to isomorphism that are not (2, 3)-cordial.

Jonathan M. Mousley, LeRoy B. Beasley, Manuel A. Santana, David E. Brown
Structural Properties of m-Ary n-Dimensional Hypercubes

The m-ary n-dimensional hypercube is a generalization of the hypercube when $$m=2$$ m = 2 . In this paper, we study the structural properties of m-ary n-dimensional hypercube by considering the structure of the resulting graph when up to approximately $$3n(m-1)$$ 3 n ( m - 1 ) vertices are deleted from it.

Saranya Anantapantula, Eddie Cheng, László Lipták
Graph Constructions Derived from Interconnection Networks

A class of interconnection networks for massively parallel processors are designed by taking copies of a building block network and wiring them together. For Dragonfly networks, the building block network is a complete graph and the wiring together is done by either a cycle or a complete graph. The process may be viewed as a way to construct a new graph from two component graphs.The resulting graph is known as a replacement graph. Furthermore, one of these constructions leads to a very large number of graphs, some of which are provably not isomorphic. The point is that the construction of a replacement in G by H requires that G be converted to a network. This paper explains the way the graph of an interconnection network is labeled and a table which is analogous to the adjacency matrix of a labeled graph. The table is used to demonstrate the nondeterminism of the concept of a replacement graph. The graph constructions are presented along with the motivating interconnection networks. The graph constructions can be generalized.

Richard Draper
On the Target Pebbling Conjecture

Graph pebbling is a network optimization model for satisfying vertex demands with vertex supplies (called pebbles), with partial loss of pebbles in transit. The pebbling number of a demand in a graph is the smallest number for which every placement of that many supply pebbles satisfies the demand. The Target Conjecture (Herscovici-Hester-Hurlbert, 2009) posits that the largest pebbling number of a demand of fixed size t occurs when the demand is entirely stacked on one vertex. This truth of this conjecture could be useful for attacking many open problems in graph pebbling, including the famous conjecture of Graham (1989) involving graph products. It has been verified for complete graphs, cycles, cubes, and trees. In this paper we prove the conjecture for 2-paths and Kneser graphs over pairs.

Glenn Hurlbert, Essak Seddiq
-Face-Magic Labelings on Even Order Projective Grid Graphs

For a graph $$G = (V, E)$$ G = ( V , E ) embedded in the projective plane, let $$\mathcal {F}(G)$$ F ( G ) denote the set of faces of G. Then, G is called a $$C_n$$ C n -face-magic projective graph if there exists a bijection $$f: V(G) \rightarrow \{1, 2, \dots , |V(G)|\}$$ f : V ( G ) → { 1 , 2 , ⋯ , | V ( G ) | } such that for any $$F \in \mathcal {F}(G)$$ F ∈ F ( G ) with $$F \cong C_n$$ F ≅ C n , the sum of all the vertex labelings along $$C_n$$ C n is a constant S. Let $$x_v =f(v)$$ x v = f ( v ) for all $$v\in V(G)$$ v ∈ V ( G ) . We call $$\{x_v : v\in V(G)\}$$ { x v : v ∈ V ( G ) } a $$C_n$$ C n -face-magic projective labeling on G. We consider the $$m \times n$$ m × n grid graph, denoted by $$\mathcal {P}_{m,n}$$ P m , n , embedded in the projective plane in the natural way. It is known that, for $$m,n\ge 2$$ m , n ≥ 2 , $$\mathcal {P}_{m,n}$$ P m , n admits a $$C_4$$ C 4 -face-magic projective labeling if and only if m and n have the same parity. When m and n are even, a $$C_4$$ C 4 -face-magic projective labeling on $$\mathcal {P}_{m,n}$$ P m , n has $$C_4$$ C 4 -face-magic value $$2mn+2$$ 2 m n + 2 . We show that there are 144 distinct $$C_4$$ C 4 -face-magic projective labelings on the $$4\times 4$$ 4 × 4 projective grid graph $$\mathcal {P}_{4,4}$$ P 4 , 4 (up to symmetries on the projective plane).

Stephen J. Curran, Stephen C. Locke
On the Locating Rainbow Connection Number of the Comb Product with Complete Graphs or Trees

This paper investigates the locating rainbow connection number ( $${ \text {rvcl}}(G)$$ rvcl ( G ) ) of comb products of graphs. We introduce the concept of a rainbow-vertex $$\ell $$ ℓ -coloring and define the locating rainbow connection number within this framework. Our main results establish tight upper and lower bounds for $${ \text {rvcl}}(G)$$ rvcl ( G ) in the context of comb products. Additionally, we determine the locating rainbow connection number for the comb product of an arbitrary graph with a complete graph or a tree.

Mahmud Imrona, A. N. M. Salman, Saladin Uttunggadewa, Pritta Etriana Putri
Cycle-Compelling Colorings of Graphs

We define a cycle-compelling coloring of a graph as a proper coloring of the vertices such that every subgraph induced by one vertex of each color contains a cycle. The cycle-compelling number is defined to be the minimum k such that some k-coloring is cycle-compelling. We provide some general bounds and algorithmic results on this and related parameters. We also investigate the value in specific graph families including cubic graphs, disjoint union of cliques, and outerplanar graphs.

Anna Bachstein, Wayne Goddard, John Xue
Harmonious Colorings of Graphs

A harmonious labeling of a graph G of order n and size m is an injective function $$f: V(G) \rightarrow \mathbb {Z}_m$$ f : V ( G ) → Z m that induces an injective function $$f': E(G) \rightarrow \mathbb {Z}_m$$ f ′ : E ( G ) → Z m defined by $$f'(uv)=f(u)+f(v) \pmod m$$ f ′ ( u v ) = f ( u ) + f ( v ) ( mod m ) . When G is a tree, then we allow f to repeat one vertex label. A proper vertex coloring $$c: V(G) \rightarrow \mathbb {Z}_k$$ c : V ( G ) → Z k is called a harmonious k-coloring if the induced edge coloring $$c': E(G) \rightarrow \mathbb {Z}_k$$ c ′ : E ( G ) → Z k defined by $$c'(uv)=c(u)+c(v) \pmod k$$ c ′ ( u v ) = c ( u ) + c ( v ) ( mod k ) is also proper. The minimum positive integer k for which G has a harmonious k-coloring is called the harmonious chromatic number of G, $$\chi _h(G)$$ χ h ( G ) . The harmonious chromatic number of all trees, cycles, grids, and graphs of diameter at most two are determined, and connections are made to existing graph labelings and colorings.

Alexis Byers, Alyssa Adams, Erica Bajo Calderon, Olivia Bindas, Madeline Cope, Andrew Summers, Rabin Thapa
A Note on the Immersion Number of Generalized Mycielski Graphs

The immersion number of a graph G, denoted $$\textrm{im}(G)$$ im ( G ) , is the largest t such that G has a $$K_t$$ K t -immersion. In this note we are interested in determining the immersion number of the m-Mycielskian of G, denoted $$\mu _m(G)$$ μ m ( G ) . Given the immersion number of G we provide a lower bound for $$\textrm{im}(\mu _m(G))$$ im ( μ m ( G ) ) . To do this we introduce the “distinct neighbor property” of immersions. We also include examples of classes of graphs where $$\textrm{im}(\mu _m(G))$$ im ( μ m ( G ) ) exceeds the lower bound. We conclude with a conjecture about $$\textrm{im}(\mu _m(K_t))$$ im ( μ m ( K t ) ) .

Karen L. Collins, Megan E. Heenehan, Jessica McDonald
Recent Developments of Star-Critical Ramsey Numbers

The star-critical Ramsey number $$r_*(G,H)$$ r ∗ ( G , H ) is the smallest integer k such that every 2-coloring of the edges of $$K_r - K_{1,r-k-1}$$ K r - K 1 , r - k - 1 contains either a red copy of G or a blue copy of H where $$r=R(G,H)$$ r = R ( G , H ) the graph Ramsey number. Since the introduction of star-critical Ramsey numbers in 2010, there have been a significant number of values discovered as well as numerous classifications of critical graphs. Some variants to the star-critical Ramsey number have been recently introduced in an attempt to further analyze when the Ramsey property is forced and to make progress on unknown Ramsey numbers. This paper will discuss recent developments of the star-critical Ramsey number and a survey will be provided for all known star-critical Ramsey numbers.

Jonelle Hook
The Zero Forcing Span of a Graph

In zero forcing, the focus is typically on finding the minimum cardinality of any zero forcing set in the graph; however, the number of cardinalities between 0 and the number of vertices in the graph for which there are both zero forcing sets and sets that fail to be zero forcing sets is not well known. In this paper, we introduce the zero forcing span of a graph, which is the number of distinct cardinalities for which there are sets that are zero forcing sets and sets that are not. We introduce the span within the context of standard zero forcing and skew zero forcing as well as for standard zero forcing on directed graphs. We characterize graphs with high span and low span of each type, and also investigate graphs with special zero forcing polynomials.

Bonnie Jacob
DNA Self-assembly: Complete Tripartite Graphs and Cocktail Party Graphs

Based on the tile method for DNA self-assembly, which involves branched junction molecules whose flexible k-arms are double strands of DNA, we design a collection of tiles that will construct a nanostructure shaped like a target graph G. We find the minimum number of tile and bond-edge types required to construct complete tripartite graphs and cocktail party graphs in three different scenarios representing distinct levels of laboratory constraints.

Leyda Almodóvar, Jane HyoJin Lee, MeiRose Neal, Heiko Todt, Jessica Williams
Inverse of Hermitian Adjacency Matrix of Mixed Bipartite Graphs

Mixed graph D is a graph that can be obtained from a graph by orienting some of its edges. The Hermitian adjacency matrix of a mixed graph is defined to be the matrix $$H=[h_{rs}]$$ H = [ h rs ] where $$h_{rs}=i$$ h rs = i if $$v_rv_s$$ v r v s is an arc in D, $$h_{rs}=-i$$ h rs = - i if $$v_sv_r$$ v s v r is an arc in D, $$h_{rs}=1$$ h rs = 1 if $$v_sv_r$$ v s v r is a digon in D and $$h_{rs}=0$$ h rs = 0 otherwise. In this paper we investigate when the hermitian adjacency matrix of a bipartite graph is invertible and we prove for any tree mixed graph T with invertible hermitian adjacency matrix that $$H^{-1}$$ H - 1 is $$\{0,\pm 1,\pm i\}$$ { 0 , ± 1 , ± i } -matrix.

Omar Alomari
Properties of Sierpinski Triangle Graphs

The Sierpinski triangle can be modeled using graphs in two different ways, resulting in classes of graphs called Sierpinski triangle graphs and Hanoi graphs. The latter are closely related to the Towers of Hanoi problem, Pascal’s triangle, and Apollonian networks. Parameters of these graphs have been studied by several researchers. We determine the number of Eulerian circuits of Sierpinski triangle graphs and present a significantly shorter proof of their domination number. We also find the 2-tone chromatic number and the number of diameter paths for both classes, generalizing the classic Towers of Hanoi problem.

Allan Bickle
Counting Vertices in Iterated Line Graphs

We introduce new methods of studying properties of iterated line graphs and demonstrate the use of these methods on a class of tree graphs. We also describe plans to generalize these methods further and derive identities for the number of vertices in the iterated line graphs of arbitrary graphs among other potential extensions of the methodology.

Zack King, Liz Lane-Harvard, Thomas Milligan
On 2-Factorizations of the Complete 3-Uniform Hypergraph of Order 12 Minus a 1-Factor

A k-factorization of the complete t-uniform hypergraph $$K^{(t)}_{v}$$ K v ( t ) is an H-decomposition of $$K^{(t)}_{v}$$ K v ( t ) where H is a k-regular spanning subhypergraph of $$K^{(t)}_{v}$$ K v ( t ) . It is known that seven of the eight non-isomorphic 3-uniform 2-regular hypergraphs of order $$v\le 9$$ v ≤ 9 factorize $$K^{(3)}_v$$ K v ( 3 ) . We use nauty to generate the 2-regular spanning subhypergraphs of $$K^{(3)}_{12}$$ K 12 ( 3 ) and show that they all factorize $$K^{(3)}_{12}-I$$ K 12 ( 3 ) - I , where I is a 1-factor.

Peter Adams, Saad I. El-Zanati, Peter Florido, William Turner
On Decompositions of Complete 3-Uniform Hypergraphs into a Linear Forest with 4 Edges

A 3-uniform linear forest is any hypergraph obtained by starting with a single 3-uniform edge and adding other 3-uniform edges sequentially such that each additional edge intersects with the previous hypergraph at no more than one vertex. There are nine such 3-uniform linear forests with four edges. In this paper we establish necessary and sufficient conditions for a decomposition of a complete 3-uniform hypergraph into isomorphic copies of a linear forest with four edges.

Ryan C. Bunge, Erin Dawson, Mary Donovan, Cody Hatzer, Jacquelyn Maass
Exterior Corners on Bargraphs of Motzkin Words

In this paper we introduce the concept of Motzkin words and Motzkin bargraphs. Over this family of bargraphs we study the exterior corner statistic. Generating functions and exact combinatorial formulas of the exterior corners are established.

Toufik Mansour, José L. Ramírez
Some Connections Between Restricted Dyck Paths, Polyominoes, and Non-Crossing Partitions

A Dyck path is a lattice path in the first quadrant of the xy-plane that starts at the origin, ends on the x-axis, and consists of the same number of North-East steps U and South-East steps D. A valley is a subpath of the form DU. A Dyck path is called restricted d-Dyck if the difference between any two consecutive valleys is at least d (right-hand side minus left-hand side) or if it has at most one valley. In this paper we give some connections between restricted d-Dyck paths and both, the non-crossing partitions of [n] and some subfamilies of polyominoes. We also give generating functions to count several aspects of these combinatorial objects.

Rigoberto Flórez, José L. Ramírez, Fabio A. Velandia, Diego Villamizar
Powers of Two as Sums of Two Balancing Numbers

The sequence of balancing numbers $$(B_n)_{n\ge 1}$$ ( B n ) n ≥ 1 is given by $$B_1=1$$ B 1 = 1 , $$B_2=6$$ B 2 = 6 , and $$B_{n}=6B_{n-1}-B_{n-2}$$ B n = 6 B n - 1 - B n - 2 for $$n\ge 3$$ n ≥ 3 . We consider the exponential Diophantine equations $$B_n=2^a$$ B n = 2 a and $$B_n+B_m=2^a$$ B n + B m = 2 a . Using Baker’s theory of logarithmic forms, Matveev’s Theorem, and an additional reduction theorem, we establish bounds on the space of possible solutions. This remaining space is sufficiently small that the problem of identifying solutions is reduced to a computational search which is carried out by a simple computer program.

Jeremiah Bartz, Bruce Dearden, Joel Iiams, Julia Peterson
Sprague-Grundy Functions for Certain Infinite Acyclic Graphs

We study the Sprague-Grundy functions of certain 2-player combinatorial games with the positive integers as the positions. One such game, called SAD (Subtract A Divisor), allows an integer to be reduced by a proper divisor. The game graph has the positive integers as vertices with a directed edge from q to $$q-d$$ q - d for each proper divisor $$d\mid q.$$ d ∣ q . This is an acyclic directed graph with only finitely many vertices reachable from each given one. It thus has, as is usual, a unique Sprague-Grundy function. It turns out that this function is the 2-adic valuation $$\nu $$ ν . If we reverse the direction of the edges the vertices are still the positive integers with a directed edge from q to $$q+d$$ q + d for any divisor $$d\mid q$$ d ∣ q including $$d=q$$ d = q . We consider the various Sprague-Grundy functions of this unbounded graph, one of which is $$\nu $$ ν . If we restrict the graph to a finite interval [1, T], there is again a unique Sprague-Grundy function, $$g_T$$ g T . We investigate $$\lim _{T \rightarrow \infty }g_T$$ lim T → ∞ g T and provide strong empirical evidence that the limit is $$\nu .$$ ν .

Aaron Meyerowitz
New Absolute Irreducibility Testing Criteria and Factorization of Multivariate Polynomials

In this chapter, we introduce a new concept of degree-gap of a multivariate polynomial. We effectively utilize this concept to present a bound on the number of absolutely irreducible factors of an infinite family of multivariate polynomials. We also show how this result can be used to guarantee that a polynomial is absolutely irreducible. We also present an algorithm for testing the absolute irreducibility of multivariate polynomials over finite fields. We discuss the ramifications and applications of our results to algebraic geometry, coding theory, cryptography, finite geometry, and other research domains.

Carlos Agrinsoni, Heeralal Janwa, Moises Delgado
Resolution of a Conjecture on the Covering Radius of Linear Codes

The covering radius of a q-ary block code C of length n is defined as the smallest integer $$R=R(C)$$ R = R ( C ) such that all vectors in $$\mathbb {F}_{q}^n$$ F q n are within Hamming distance R of some codeword of C. By [n, k, d]R code, we mean an [n, k, d] code having covering radius R. The covering radius of a code is one of the fundamental parameters of a code and gives its suitability for data compression, list decoding radius, and has many other applications. The upper bound of Janwa (1986) relates all the fundamental parameters as $$R(C)\le \mathscr {H}(C):=n-\sum _{i=1}^{k}\lceil \frac{d}{2^i} \rceil $$ R ( C ) ≤ H ( C ) : = n - ∑ i = 1 k ⌈ d 2 i ⌉ . Which can be expressed as $$n-g_{q}+d-\lceil d/q^{k}\rceil $$ n - g q + d - ⌈ d / q k ⌉ . If $$n_{q}(k,d)$$ n q ( k , d ) denotes the minimum length of any code of dimension k and distance over $$\mathbb {F}_{q}$$ F q it was conjectured by Janwa that under certain conditions $$g_{q}(k,d)$$ g q ( k , d ) (the Griesmer length) can be replaced by $$n_{q}(k,d)$$ n q ( k , d ) . Janwa (1989) and Janwa and Mattson (1999), proved three of the four cases and conjectured that the final case is true. In this article, we give a resolution of this conjecture. These bounds have helped us in determing the exact covering radius of codes from Hermitian curves in most cases, and yielding close bounds in the rest of them.

Juan Carlos Orozco, Heeralal Janwa
Quantum Error-Correcting Codes Over Small Fields From AG Codes

To overcome decades of obstacles and constraints implied by the no-cloning theorem, Calderbank and Shor constructed codes to control errors in quantum computers. Their construction uses a pair of binary or quaternary error-control codes for classical channels. Classic codes such as Reed-Muller codes provide such pairs. However, their performance is not so good. In this article we use codes from algebraic curves over high degree extensions of $$\mathbb {F}_2$$ F 2 to construct the self–orthogonal binary code or quaternary code pairs. We also present some results on the parameters of the resulting subfield codes over $$\mathbb {F}_2$$ F 2 or $$\mathbb {F}_4$$ F 4 from Hermitian curves, Norm–Trace curves, quasi–Hermitian curves, Castle curves and others. Several of these results are novel and provide a pathway to make progress towards making quantum computers feasible and practical during the next decade.

Heeralal Janwa, Fernando L. Piñero–González
A Go-Up Code Construction from Linear Codes Yielding Additive Codes for Quantum Stabilizer Codes

Given a code C over the finite field $$\mathbb {F}_q$$ F q , where q is a power of a prime number, some constructions exist that permit us to obtain a new code from C over $$\mathbb {F}_q$$ F q or over a subfield of $$\mathbb {F}_q$$ F q , such as subfield subcodes. However in some important applications, one needs codes over an extension field, for example in quantum error-correcting codes (QECC). We propose a technique that we call Go-Up construction, which allows us to obtain an additive or a linear code over $$\mathbb {F}_{q^m}$$ F q m from any set of m linear codes over $$\mathbb {F}_q$$ F q . We show under what condition this code is a self-orthogonal or self-dual code. Thus we are able to give new constructions of quantum stabilizer codes from our codes that are additive. We present several such classes of QECC. Our GU codes also have applications to algebraic coding theory, finite geometries, finite group theory, and also to combinatorial objects such as strongly regular graphs, and few-weight codes (see [3]).

Arrieta A. Eddie, Heeralal Janwa
Bent and Near-Bent Function Construction and 2-Error-Correcting Codes

A function $$f: F_{2^m} \rightarrow F_{2^t}$$ f : F 2 m → F 2 t is called a vectorial Boolean function in m variables. Whenever $$t = 1$$ t = 1 we call these functions Boolean functions. In this work, we study the construction of Gold and Kasami-Welch functions of the form $$Tr(\lambda x^d)$$ T r ( λ x d ) (for $$d = 2^{l} + 1, 2^{2l} - 2^{l} + 1$$ d = 2 l + 1 , 2 2 l - 2 l + 1 and $$\lambda \in F_{2^m}^{*}$$ λ ∈ F 2 m ∗ ). These functions’ nonlinearity property is a measure of their distance to the set of affine functions (the first-order Reed-Muller codes). We generalize a result of Dillon and Dobbertin for conditions under which these functions are bent. We give algorithms that generate and determine the bentness of the functions. We construct 2-error-correcting cyclic codes utilizing Almost-Perfect-Nonlinear (APN) and near-bent exponents. We present theorems that enumerate the Gold and Kasami-Welch functions. We improve previous algorithms used to determine the minimum distance of these codes.

Jose W. Velazquez, Heeralal Janwa
Metadata
Title
Combinatorics, Graph Theory and Computing
Editors
Frederick Hoffman
Sarah Holliday
Zvi Rosen
Farhad Shahrokhi
John Wierman
Copyright Year
2024
Electronic ISBN
978-3-031-52969-6
Print ISBN
978-3-031-52968-9
DOI
https://doi.org/10.1007/978-3-031-52969-6

Premium Partner