Combinatorics, Graph Theory and Computing

Frontmatter

Additive Combinatorics in Groups and Geometric Combinatorics on Spheres

Abstract

We embark on a tour that takes us through four closely related topics: the dual concepts of independence and spanning in finite abelian groups and the analogous dual concepts of designs and distance sets on spheres. We review some of the main known results in each area, mention several open questions, and discuss some connections among these four interesting topics.

Béla Bajnok

A Walk Through Some Newer Parts of Additive Combinatorics

Abstract

In this survey chapter we discuss some recent results and related open questions in additive combinatorics, in particular, questions about sumsets in finite abelian groups.

Béla Bajnok

Passing Drops and Descents

Abstract

We consider generalizations of drops and descents from permutations to arrangements of sets with repetition. We also establish a generalization of Worpitzky’s identity in the special case when all elements in the set repeat equally often by way of counting passing patterns among jugglers in two different ways.

Cailyn Bass, Steve Butler

Group Divisible Designs with Three Groups and Block Size 4

Abstract

Group divisible designs are classical combinatorial designs studied for their applications as well as for their own sake. They provide an ample opportunity of developing techniques to study combinatorial design constructions. GDDs are inherently hard to construct, especially when the number of groups is less than the block size and group sizes are different. The subject matter for this chapter is GDDs of block size four with three groups of different sizes. A previous study of the problem addressed the cases when the first group size, say \(n_1\) is 1 or 2, the second group size \(n_2=n\) greater than or equal to \(n_1\) and the third group size is \(n + 1\). The first part of the present paper tackles again the case of the first group having size one and the third group having size \(n + 2\). We also obtain several non-existence results when restrictions on block configurations are placed. The second part of the chapter deals with group sizes 3, n \( (n \ge 3)\) and \(n + 1\), respectively. We hope that these constructions of specific families will help to develop a more unified approach to construct such GDDs.

Dinesh G. Sarvate, Dinkayehu M. Woldemariam, Li Zhang

A New Absolute Irreducibility Criterion for Multivariate Polynomials over Finite Fields

Abstract

One of the key problems in algebraic geometry and its applications in coding theory, cryptography, and other disciplines is to determine whether a variety defined by a set of polynomials is absolutely irreducible; i.e., it remains irreducible in the algebraic closure of the defining field. The famous Eisenstein criterion for irreducibility works only over the defining fields. One important place where this is needed is when one applies the Riemann-Roch theorem. Another important application is in bounding the number of rational points or exponential sums through the Weil conjectures. In this chapter, we consider the hypersurfaces defined by generalized trinomials. We present a new absolute irreducibility criterion for generalized trinomials over finite fields. Our criterion does not require testing for irreducibility in the ground field or in any extension field. We just require multivariate GCD computations and the square-free property. Since almost all polynomials are known to be square-free, our absolute irreducibility criterion proves the absolute irreducibility of almost all generalized trinomials.

Carlos Agrinsoni, Heeralal Janwa, Moises Delgado

On Combinatorial Interpretations of Some Elements of the Riordan Group

Abstract

Riordan arrays, equipped with Shapiro’s multiplication rule, form a group and this group provides an interesting algebraic framework to solve combinatorial problems. In this chapter, we provide combinatorial interpretations for Riordan arrays of the form \(R = (g(z), zg(z))\), where \(g(z)\) is a generating function satisfying a functional equation \(g(z) = 1 + z*{g(z)}^k\), where k is a positive integer greater than or equal to 2. The combinatorial interpretations are then used to obtain the inverses of these elements of the Bell subgroup of the Riordan group explicitly in terms of powers of \(g(z)\).

Melkamu Zeleke, Mahendra Jani

Production Matrices of Double Riordan Arrays

Abstract

A double Riordan array is an infinite lower triangular matrix, denoted by \( (g; f_1, f_2)\), where g, \(f_1\), and \(f_2\) are generating functions. The coefficients of the generating function g gives the first column of the matrix, and the remaining columns are found by multiplying the previous column by alternating \(f_1\) and \(f_2\). In other words,

$$\displaystyle (g; f_1, f_2)=(g, gf_1, gf_1f_2,g{f_1}^2f_2, gf_1^2f_2^2,\dots ). $$

This is the columns construction of a double Riordan array. We can determine the elements of a double Riordan array using A- and Z-sequences which gives a row construction of a double Riordan array, see ([2] and [5]). In this chapter we define the production matrix of a double Riordan array, and show how it can be used to determine the A- and Z-sequences.

Dennis Davenport, Fatima Fall, Julian Francis, Trinity Lee

The Existence of a Knight’s Tour on the Surface of Rectangular Boxes

Abstract

A knight’s tour is a sequence of knight’s moves such that each square on the board is visited exactly once. In this chapter, we show that a closed knight’s tour exists on the surface of a rectangular box of any size. Our general algorithm is to concatenate the top and bottom faces of a box with its side faces. When general criteria are not satisfied, especially when the dimensions of the rectangular box are small, we devise some special techniques to cover these cases.

Shengwei Lu, Carl Yerger

A New Upper Bound for the Site Percolation Threshold of the Square Lattice

Abstract

The upper bound for the site percolation threshold of the square lattice is reduced from 0.679492 to 0.666894, providing the first improvement since 1995. The bound is obtained by using the substitution method with new computational reductions which make calculations for site models more efficient. The substitution method is applied, comparing the site percolation model on a self-matching lattice to the square lattice site percolation model in a two-stage process.

John C. Wierman, Samuel P. Oberly

Prime, Composite and Fundamental Kirchhoff Graphs

Abstract

A Kirchhoff graph is a vector graph with orthogonal cycles and vertex cuts. An algorithm has been developed that constructs all the Kirchhoff graphs up to a fixed edge multiplicity. This algorithm is used to explore the structure of prime Kirchhoff graph tilings. The existence of infinitely many prime Kirchhoff graphs for a given set of fundamental Kirchhoff graphs is established, as is the existence of a minimal multiplicity for Kirchhoff graphs to exist.

Jessica Wang, Joseph D. Fehribach

On the Minimum Locating Number of Graphs with a Given Order

Abstract

A locating set S in a connected graph is a set of vertices satisfying that \(N(u)\cap S\) is unique for each vertex u not in S. A locating set can be considered as a set of sensors which can determine the exact location of an intruder. The size of a smallest locating set of a graph G is called the locating number of the graph and denoted by \(ln(G)\). We show that \(min\, \{ln(G): G \) is a connected graph with n vertices \(\} = s\) when \(2^{s-1}+(s-1) < n \leq 2^s+s\).

Sul-young Choi, Puhua Guan

j-Multiple, k-Component Order Neighbor Connectivity

Abstract

Consider a network modeled by a graph G on n nodes and e edges. There exist several parameters to determine the vulnerability of G. One such parameter is the domination number, which measures the minimum number of nodes necessary in a set so that its closed neighborhood is the entire graph. Multiple domination, sometimes referred to as j-domination, is a variety of domination that requires every node to either be in the set or adjacent to at least j nodes from it. The vulnerability parameter k-component order neighbor connectivity is an extension of domination and is defined as the minimum number of nodes that when removed along with their neighbors leave only components of order less than k. The new parameter, j-multiple, k-component order neighbor connectivity, denoted \(\kappa _{nc,j}^{(k)}\), extends both concepts and is defined as the minimum number of nodes that need to be removed, along with their neighbors, such that the surviving subgraph contains only components of order at most k and every node outside of the set that is adjacent to it is adjacent to at least j nodes from it. The complexity of computing the value for this parameter is NP-hard since it coincides with j-domination when k is 1. Here we introduce this new parameter, establish its bounds, and compare it to several other previously established parameters. We also establish formulas for \(\kappa _{nc,j}^{(k)}\) for several classes of graphs, including complete and complete bipartite graphs as well as paths, cycles, wheels, and complete grid graphs.

Alexis Doucette, Charles Suffel

Graphic Approximation of Integer Sequences

Abstract

A variety of network modeling problems begin by generating a degree sequence drawn from a given probability distribution. If the randomly generated sequence is not graphic, we give two new approaches for generating a graphic approximation of the sequence. These schemes are fast, simple to implement, and only require a linear amount of memory. This allows approximation to be performed on very large integer sequences.

Brian Cloteaux

Changing the Uniform Spectrum by Deleting Edges

Abstract

A graph is said to be k-uniformly connected if there exists a path of length k between each pair of vertices. This generalizes the well-known concept of a Hamiltonian-connected graph—a graph, order n, in which there exits a Hamiltonian path (path of length \(n-1\)) between each pair of vertices. That is, a graph is Hamiltonian-connected if and only if it is \((n-1)\)-uniformly connected. One can also say a graph is complete if and only if it is 1-uniformly connected. The uniform spectrum of a graph G is the set of all k for which G is k-uniformly connected. In this chapter, we investigate the impact of adding or deleting vertices or edges on the uniform spectrum of a graph. Some general results are presented as well as analyses of specific classes of graphs such as bipartite graphs and wheels.

Drake Olejniczak, Robert Vandell

Strongly Regular Multigraphs

Abstract

A family of regular graphs which have a direct connection to structures in algebraic combinatorics are strongly regular graphs. These graphs are defined by 4 parameters, n, k, a, and c, where n is the number of nodes, k is the degree of each node, a is the number of common neighbors for every adjacent pair of nodes, and c is the number of common neighbors for every nonadjacent pair of nodes. A multigraph is a graph that has no self-loops, but may have multiple edges and is formally defined by specifying a graph G and assigning a multiplicity to each edge of G. We examine underlying strongly regular multigraphs in order to further clarify their properties, specifically with regard to combinatorial configurations.

Leah H. Meissner, John T. Saccoman

Geodesic Leech Graphs

Abstract

Let \(f:E\rightarrow \{1,2,3,\dots \}\) be an edge labeling of G. The weight of a path P is the sum of the labels assigned to the edges of P. The edge labeling f is called a geodesic Leech labeling, if the set of weights of the geodesic paths in G is \(\{1,2,3,\dots ,t_{gp}(G)\}\), where \(t_{gp}(G)\), the geodesic path number of G, is the number of geodesic paths in G. A graph which admits a geodesic Leech labeling is called a geodesic Leech graph. In this chapter, we prove the existence of infinite families of geodesic Leech graphs. It is also proved that \(C_5\) is not a geodesic Leech graph. Some open problems in this area are also included.

Seena Varghese, Aparna Lakshmannan S., S. Arumugam

Characterizing s-Strongly Chordal Graphs Using 2-Paths and k-Chords

Abstract

A well-known 1961 characterization of chordal graphs by G. A. Dirac in terms of simplicial vertices, was extended by Chvátal, Rusu, and Sritharan (Discrete Math., 2002) to a natural sequence of “weakly chordal graphs.” Somewhat similarly, we will start from the same place and characterize a natural sequence of “chordal, strongly chordal, …, s-strongly chordal, …” graphs, except now in terms of 2-path graphs (meaning graphs that are either \(K_3\) or a 2-tree graph with exactly two degree-2 vertices—equivalently, “paths of triangles” that are the 2-connected outerplanar strongly chordal graphs).

Terry A. McKee

The Spectrum Problem for the 4-Uniform 4-Colorable 3-Cycles with Maximum Degree 2

Abstract

The complete t-uniform hypergraph of order v, denoted \(K^{(t)}_v\), has a set V  with v elements as its vertex set and the set of all t-element subsets of V  as its edge set. For the purposes of this work, we define a 4-uniform 3-cycle of maximum degree 2 to be any 4-uniform hypergraph of maximum degree 2 that can be obtained by adding two vertices to each of the three edges in \(K^{(2)}_3\). There are five such 4-uniform hypergraphs up to isomorphism. Two of them have chromatic number 4. We give necessary and sufficient conditions for the existence of a decomposition of the complete 4-uniform hypergraph of order v into these 4-colorable 3-cycles.

Ryan C. Bunge, Saad I. El-Zanati, Julie N. Kirkpatrick, Shania M. Sanderson, Michael J. Severino, William F. Turner

A Matrix Criterion for Harmonic Morphisms of Graphs with Applications to Graph Products

Abstract

Urakawa, and later Baker and Norine, developed the notion of a harmonic morphism as a type of graph morphism with similar properties to holomorphic maps of Riemann surfaces. We give a matrix criterion for harmonic graph morphisms which allows us to translate combinatorial questions about harmonic morphisms to linear algebra questions. We illustrate its use by finding conditions under which certain maps of NEPS graph products (for example, tensor, Cartesian, and strong products) are harmonic, and calculating their vertical and horizontal multiplicity matrices and degrees. We also apply the matrix criterion to lexicographic products, the special case of graph blow-ups, and graph joins.

Caroline G. Melles, David Joyner

Applications of Topological Graph Theory to 2-Manifold Learning

Abstract

We show how, given a sufficiently large point cloud sampled from an embedded 2-manifold in \(\mathbb {R}^n\), we may obtain a global representation of the embedded manifold as a cell complex with vertices given by a representative subset of the point cloud. We apply a known projection based approach (into approximations of tangent planes) from the studies of surface reconstruction and computer graphics, and we extend this with the application of techniques from topological graph theory for the purpose of topological identification of the sampled surface. We apply our methods to samples taken from orientable and nonorientable surfaces. Since our new approach is based on a cell complex rather than a triangulation, it does not derive from or apply Vornoi diagrams or any Delaunay structure.

Tyrus Berry, Steven Schluchter

Properties of Sierpinski Triangle Graphs

Abstract

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 study 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 pairs of vertices at maximum distance for both classes, generalizing the classic Towers of Hanoi problem.

Allan Bickle

Decomposing the -Fold Complete 3-Uniform Hypergraph into the Lines of the Pasch Configuration

Abstract

Let P denote the 3-uniform hypergraph on 6 vertices whose edges form the lines of the Pasch configuration. We give necessary and sufficient conditions for the existence of P-decompositions of the \(\lambda \)-fold complete 3-uniform hypergraph on v vertices.

Ryan C. Bunge, Skyler R. Dodson, Saad I. El-Zanati, Jacob Franzmeier, Dru Horne

On Decompositions of the Johnson Graph

Abstract

Most of the results on graph decompositions involve a partition of the edges of the complete graph, complete bipartite graph, or complete multipartite graph into disjoint copies of one or more small graphs. In this chapter we find conditions for the decompositions of the Johnson graph into a variety of smaller subgraphs including cycles, path, and other common subgraphs.

Atif Abueida, Mike Daven

Tiling With Three Element Sets

Abstract

We consider tilings of intervals and other sets in \(\mathbb {Z}\) with translates of a three element integer set \(\mathcal {A}=\{0,a,a+b\}\) and its reflection \(\mathcal {B}=\{0,b,a+b\}.\) We also consider these questions for intervals and other sets in \(\mathbb {R}\) where a and b are real numbers.

Aaron Meyerowitz

Deques on a Torus

Abstract

We provide an overview of graphical representations of stacks, queues, and deques. In the case of a cylinder book, corresponding to a deque, we give edge bounds and determine the deque number of the complete graph. We extend the deque in a natural way, forming a toroidal deque. Unlike the other three structures, the toroidal deque can process certain non-planar graphs, including \(K_7\) and the Cartesian product of two cycles.

Thomas McKenzie, Shannon Overbay

Möbius Book Embeddings

Abstract

Book embeddings of graphs have been the subject of extensive study. In this chapter we generalize the definition of such embeddings by allowing book pages to be Möbius strips, rather than half planes. We give an application of these Möbius books and we give page bounds for complete graphs and bipartite graphs. We conclude with optimal Möbius book embeddings of some well-known graph families.

Nicholas Linthacum, Luke Martin, Thomas McKenzie, Shannon Overbay, Lin Ai Tan

DNA Self-assembly: Friendship Graphs

Abstract

Based on the flexible tile method for DNA self-assembly, we find a collection of tiles that will construct a nanostructure shaped like a friendship graph or a dumbbell-friendship graph. We find the minimum number of tile and bond-edge types required to construct these graphs in three different scenarios representing distinct levels of laboratory constraints.

Leyda Almodóvar, Emily Brady, Michaela Fitzgerald, Hsin-Hao Su, Heiko Todt

The Pansophy of Semi Directed Graphs

Abstract

Given an ordered list of randomly-selected pairs of vertices in a graph, how many of these pairs can be connected with disjoint paths? The pansophy of a graph G is the expected number of possible disjoint paths—this has been calculated and studied for many classes of undirected graphs. In this chapter we study the pansophy of various graphs where an edge or a select collection of edges have been directed. By doing this, how is the pansophy of G affected? Do specific selections of edges affect pansophy differently from other selections? These and other questions are addressed in this chapter.

Jeffe Boats, Lazaros Kikas

Signed Magic Arrays with Certain Property

Abstract

A signed magic array, \(SMA(m, n;s,t)\), is an \(m \times n\) array with the same number of filled cells s in each row and the same number of filled cells t in each column, filled with a certain set of numbers that is symmetric about the number zero, such that every row and column has a zero sum. We use the notation \(SMA(m, n)\) if \(m=t\) and \(n=s\).

In this chapter, we prove that for every even number \(n\geq 2\) there exists an \(SMA(m,n)\) such that the entries \(\pm x\) appear in the same row for every \(x\in \{1, 2, 3,\ldots , mn/2\}\) if and only if (a) \(n=2\) and \(m\equiv 0, 3\pmod 4\), or (b) \(n\geq 4\) and \(m\geq 3\).

Abdollah Khodkar, David Leach

The Buratti-Horak-Rosa Conjecture Holds for Some Underlying Sets of Size Three

Abstract

The Buratti-Horak-Rosa Conjecture concerns the possible multisets of edge-labels of a Hamiltonian path in the complete graph with vertex labels \(0, 1, \ldots , {v-1}\) under a particular induced edge-labeling. The conjecture has been shown to hold when the underlying set of the multiset has size at most 2, is a subset of \(\{1,2,3,4\}\) or \(\{1,2,3,5\}\), or is \(\{1,2,6\}\), \(\{1,2,8\}\) or \(\{1,4,5\}\), as well as partial results for many other underlying sets. We use the method of growable realizations to show that the conjecture holds for each underlying set \(U = \{ x,y,z \}\) when \(\max (U) \leq 7\) or when \(xyz \leq 24\), with the possible exception of \(U = \{1,2,11\}\). We also show that for any even x the validity of the conjecture for the underlying set \(\{ 1,2,x \}\) follows from the validity of the conjecture for finitely many multisets with this underlying set.

Pranit Chand, M. A. Ollis