# Discrete Mathematics and Combinatorics Commons™

Articles 1 - 30 of 960

## Full-Text Articles in Discrete Mathematics and Combinatorics

List-Distinguishing Cartesian Products Of Cliques, Michael Ferrara, Zoltan Füredi, Sogol Jahanbekam, Paul Wenger Jun 2019

#### List-Distinguishing Cartesian Products Of Cliques, Michael Ferrara, Zoltan Füredi, Sogol Jahanbekam, Paul Wenger

##### Sogol Jahanbekam

The distinguishing number of a graph G, denoted D(G), is the minimum number of colors needed to produce a coloring of the vertices of G so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment L on a graph G is a function that assigns each vertex of G a set of colors. An L-coloring of G is a coloring in which each vertex is colored with a color from L(v). The list distinguishing number of G, denoted Dℓ(G) is the minimum k such that every list assignment L that assigns a list ...

The Determinant And Complex Gershgorin Circles, Florian Bünger, Siegfried M. Rump 428783027 May 2019

#### The Determinant And Complex Gershgorin Circles, Florian Bünger, Siegfried M. Rump 428783027

##### Electronic Journal of Linear Algebra

Each connected component of the Gershgorin circles of a matrix contains exactly as many eigenvalues as circles are involved. Thus, the Minkowski (set) product of all circles contains the determinant if all circles are disjoint. In [S.M. Rump. Bounds for the determinant by Gershgorin circles. Linear Algebra and its Applications, 563:215--219, 2019.], it was proved that statement to be true for real matrices whose circles need not to be disjoint. Moreover, it was asked whether the statement remains true for complex matrices. This note answers that in the affirmative. As a by-product, a parameterization of the outer loop ...

On The Intersection Number Of Finite Groups, Humberto Bautista Serrano May 2019

#### On The Intersection Number Of Finite Groups, Humberto Bautista Serrano

##### Math Theses

Let G be a finite, nontrivial group. In a paper in 1994, Cohn defined the covering number of a finite group as the minimum number of nontrivial proper subgroups whose union is equal to the whole group. This concept has received considerable attention lately, mainly due to the importance of recent discoveries. In this thesis we study a dual concept to the covering number. We define the intersection number of a finite group as the minimum number of maximal subgroups whose intersection is equal to the Frattini subgroup. Similarly we define the inconjugate intersection number of a finite group as ...

Behind The Tiles: Mathematics Of Carcassonne, Emilia Dewyngaert May 2019

#### Behind The Tiles: Mathematics Of Carcassonne, Emilia Dewyngaert

##### Across the Bridge: The Merrimack Undergraduate Research Journal

Carcassonne is a tile-placing game where players take turns choosing a tile from a stack and attempting to create a city, road or a meadow. In addition to this, there is a river expansion pack that has river tiles to be placed. This paper focuses on how many different layouts or configurations of the river expansion pack can be created. It also discusses the Matlab code adapted to create a simulation of possible configurations of the river expansion pack.

Maximum Oriented Forcing Number For Complete Graphs, Yair Caro, Ryan Pepper May 2019

#### Maximum Oriented Forcing Number For Complete Graphs, Yair Caro, Ryan Pepper

##### Theory and Applications of Graphs

The \emph{maximum oriented $k$-forcing number} of a simple graph $G$, written $\MOF_k(G)$, is the maximum \emph{directed $k$-forcing number} among all orientations of $G$. This invariant was recently introduced by Caro, Davila and Pepper in~\cite{CaroDavilaPepper}, and in the current paper we study the special case where $G$ is the complete graph with order $n$, denoted $K_n$. While $\MOF_k(G)$ is an invariant for the underlying simple graph $G$, $\MOF_k(K_n)$ can also be interpreted as an interesting property for tournaments. Our main results further focus on the case when $k=1$. These include a ...

Proof Of A Conjecture Of Graham And Lovasz Concerning Unimodality Of Coefficients Of The Distance Characteristic Polynomial Of A Tree, Ghodratollah Aalipour, Aida Abiad, Zhanar Berikkyzy, Leslie Hogben, Franklin H.J. Kenter, Jephian C.-H. Lin, Michael Tait May 2019

#### Proof Of A Conjecture Of Graham And Lovasz Concerning Unimodality Of Coefficients Of The Distance Characteristic Polynomial Of A Tree, Ghodratollah Aalipour, Aida Abiad, Zhanar Berikkyzy, Leslie Hogben, Franklin H.J. Kenter, Jephian C.-H. Lin, Michael Tait

##### Leslie Hogben

The conjecture of Graham and Lov ́asz that the (normalized) coefficients of the distance characteristic polynomial of a tree are unimodal is proved; it is also shown that the (normalized) coefficients are log-concave. Upper and lower bounds on the location of the peak are established.

Multi-Part Nordhaus-Gaddum Type Problems For Tree-Width, Colin De Verdière Type Parameters, And Hadwiger Number, Leslie Hogben, Jephian C.-H. Lin, Michael Young May 2019

#### Multi-Part Nordhaus-Gaddum Type Problems For Tree-Width, Colin De Verdière Type Parameters, And Hadwiger Number, Leslie Hogben, Jephian C.-H. Lin, Michael Young

##### Leslie Hogben

A traditional Nordhaus-Gaddum problem for a graph parameter β is to find a (tight) upper or lower bound on the sum or product of β(G)and β(G¯) (where G¯ denotes the complement of G). An r-decomposition G1,…,Gr of the complete graph Kn is a partition of the edges of Kn among r spanning subgraphs G1,…,Gr. A traditional Nordhaus-Gaddum problem can be viewed as the special case for r=2 of a more general r-part sum or product Nordhaus-Gaddum type problem. We determine the values of the r-part sum and product upper bounds asymptotically as n goes ...

Graphs That Are Cospectral For The Distance Laplacian, Boris Brimkov, Ken Duna, Leslie Hogben, Kate Lorenzen, Carolyn Reinhart, Sung-Yell Song, Mark Yarrow May 2019

#### Graphs That Are Cospectral For The Distance Laplacian, Boris Brimkov, Ken Duna, Leslie Hogben, Kate Lorenzen, Carolyn Reinhart, Sung-Yell Song, Mark Yarrow

##### Leslie Hogben

The distance matrix D(G) of a graph G is the matrix containing the pairwise distances between vertices, and the distance Laplacian matrix is DL(G)=T(G)−D(G), where T(G) is the diagonal matrix of row sums of D(G). We establish several general methods for producing DL-cospectral graphs that can be used to construct infinite families. We provide examples showing that various properties are not preserved by DL-cospectrality, including examples of DL-cospectral strongly regular and circulant graphs. We establish that the absolute values of coefficients of the distance Laplacian characteristic polynomial ...

Cop Throttling Number: Bounds, Values, And Variants, Anthony Bonato, Jane Breen, Boris Brimkov, Joshua Carlson, Sean English, Jesse Geneson, Leslie Hogben, K. E. Perry, Carolyn Reinhart May 2019

#### Cop Throttling Number: Bounds, Values, And Variants, Anthony Bonato, Jane Breen, Boris Brimkov, Joshua Carlson, Sean English, Jesse Geneson, Leslie Hogben, K. E. Perry, Carolyn Reinhart

##### Leslie Hogben

The cop throttling number thc(G) of a graph G for the game of Cops and Robbers is the minimum of k+captk(G), where k is the number of cops and captk(G) is the minimum number of rounds needed for k cops to capture the robber on G over all possible games in which both players play optimally. In this paper, we answer in the negative a question from [Breen et al., Throttling for the game of Cops and Robbers on graphs, {\em Discrete Math.}, 341 (2018) 2418--2430.] about whether the cop throttling number of any graph is ...

#### Nordhaus-Gaddum Problems For Colin De Verdière Type Parameters, Variants Of Tree-Width, And Related Parameters, Leslie Hogben

##### Leslie Hogben

A Nordhaus-Gaddum problem for a graph parameter is to determine a tight lower or upper bound for the sum or product of the parameter evaluated on a graph and on its complement. This article surveys Nordhaus-Gaddum results for the Colin de Verdiere type parameters mu, nu, and xi; tree-width and its variants largeur d'arborescence, path-width, and proper path-width; and minor monotone ceilings of vertex connectivity and minimum degree.

Spn Graphs And Rank-1 Cp-Completable Graphs, Leslie Hogben, Naomi Shaked-Monderer May 2019

#### Spn Graphs And Rank-1 Cp-Completable Graphs, Leslie Hogben, Naomi Shaked-Monderer

##### Leslie Hogben

A simple graph G is an SPN graph if every copositive matrix having graph G is the sum of a positive semidefinite and nonnegative matrix. SPN graphs were introduced in [Shaked-Monderer, SPN graphs: When copositive = SPN, Linear Algebra Appl., 509(15):82-113, 2016], where it was conjectured that the complete subdivision graph of K4 is an SPN graph. We disprove this conjecture, which in conjunction with results in the Shaked-Monderer paper show that a subdivision of K4 is a SPN graph if and only if at most one edge is subdivided. We conjecture that a graph is an SPN graph ...

Zero Forcing And Maximum Nullity For Hypergraphs, Leslie Hogben May 2019

#### Zero Forcing And Maximum Nullity For Hypergraphs, Leslie Hogben

##### Leslie Hogben

The concept of zero forcing is extended from graphs to uniform hypergraphs in analogy with the way zero forcing was defined as an upper bound for the maximum nullity of the family of symmetric matrices whose nonzero pattern of entries is described by a given graph: A family of symmetric hypermatrices is associated with a uniform hypergraph and zeros are forced in a null vector. The value of the hypergraph zero forcing number and maximum nullity are determined for various families of uniform hypergraphs and the effects of several graph operations on the hypergraph zero forcing number are determined. The ...

Rigid Linkages And Partial Zero Forcing, Daniela Ferrero, Mary Flagg, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Seth A. Meyer, Shahla Nasserasr, Bryan Shader May 2019

#### Rigid Linkages And Partial Zero Forcing, Daniela Ferrero, Mary Flagg, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Seth A. Meyer, Shahla Nasserasr, Bryan Shader

##### Leslie Hogben

Connections between vital linkages and zero forcing are established. Specifically, the notion of a rigid linkage is introduced as a special kind of unique linkage and it is shown that spanning forcing paths of a zero forcing process form a spanning rigid linkage and thus a vital linkage. A related generalization of zero forcing that produces a rigid linkage via a coloring process is developed. One of the motivations for introducing zero forcing is to provide an upper bound on the maximum multiplicity of an eigenvalue among the real symmetric matrices described by a graph. Rigid linkages and a related ...

The Inverse Eigenvalue Problem Of A Graph: Multiplicities And Minors, Wayne Barrett, Steve Butler, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Bryan L. Shader, Michael Young May 2019

#### The Inverse Eigenvalue Problem Of A Graph: Multiplicities And Minors, Wayne Barrett, Steve Butler, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Bryan L. Shader, Michael Young

##### Leslie Hogben

The inverse eigenvalue problem of a given graph G is to determine all possible spectra of real symmetric matrices whose off-diagonal entries are governed by the adjacencies in G. Barrett et al. introduced the Strong Spectral Property (SSP) and the Strong Multiplicity Property (SMP) in [8]. In that paper it was shown that if a graph has a matrix with the SSP (or the SMP) then a supergraph has a matrix with the same spectrum (or ordered multiplicity list) augmented with simple eigenvalues if necessary, that is, subgraph monotonicity. In this paper we extend this to a form of minor ...

The Principal Rank Characteristic Sequence Over Various Fields, Wayne Barrett, Steve Butler, Minerva Catral, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, P. Van Den Driessche, Michael Young May 2019

#### The Principal Rank Characteristic Sequence Over Various Fields, Wayne Barrett, Steve Butler, Minerva Catral, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, P. Van Den Driessche, Michael Young

##### Leslie Hogben

Given an n x n matrix, its principal rank characteristic sequence is a sequence of length n+1 of 0s and 1s where, for k = 0, 1, . . . , n, a 1 in the kth position indicates the existence of a principal submatrix of rank k and a 0 indicates the absence of such a submatrix. The principal rank characteristic sequences for symmetric matrices over various fields are investigated, with all such attainable sequences determined for all n over any field with characteristic 2. A complete list of attainable sequences for real symmetric matrices of order 7 is reported.

Matching Preclusion Of The Generalized Petersen Graph, Ajay Arora, Eddie Cheng, Christopher Melekian May 2019

#### Matching Preclusion Of The Generalized Petersen Graph, Ajay Arora, Eddie Cheng, Christopher Melekian

##### Theory and Applications of Graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph with no perfect matchings. In this paper we determine the matching preclusion number for the generalized Petersen graph $P(n,k)$ and classify the optimal sets.

Perfect Double Roman Domination Of Trees, Ayotunde Egunjobi May 2019

#### Perfect Double Roman Domination Of Trees, Ayotunde Egunjobi

##### Electronic Theses and Dissertations

See supplemental content for abstract

Taking Notes: Generating Twelve-Tone Music With Mathematics, Nathan Molder May 2019

#### Taking Notes: Generating Twelve-Tone Music With Mathematics, Nathan Molder

##### Electronic Theses and Dissertations

There has often been a connection between music and mathematics. The world of musical composition is full of combinations of orderings of diﬀerent musical notes, each of which has diﬀerent sound quality, length, and em phasis. One of the more intricate composition styles is twelve-tone music, where twelve unique notes (up to octave isomorphism) must be used before they can be repeated. In this thesis, we aim to show multiple ways in which mathematics can be used directly to compose twelve-tone musical scores.

Apr 2019

#### Mathematical Models: The Lanchester Equations And The Zombie Apocalypse, Hailey Bauer

##### Undergraduate Theses and Capstone Projects

This research study used mathematical models to analyze and depicted specific battle situations and the outcomes of the zombie apocalypse. The original models that predicted warfare were the Lanchester models, while the zombie apocalypse models were fictional expansions upon mathematical models used to examine infectious diseases. In this paper, I analyzed and compared different mathematical models by examining each model’s set of assumptions and the impact of the change in variables on the population classes. The purpose of this study was to understand the basics of the discrete dynamical systems and to determine the similarities between imaginary and realistic ...

Series-Parallel Operations With Alpha-Graphs, Christian Barrientos, Sarah Minion Apr 2019

#### Series-Parallel Operations With Alpha-Graphs, Christian Barrientos, Sarah Minion

##### Theory and Applications of Graphs

Among difference vertex labelings of graphs, $\alpha$-labelings are the most restrictive one. A graph is an $\alpha$-graph if it admits an $\alpha$-labeling. In this work, we study a new alternative to construct $\alpha$-graphs using, the well-known, series-parallel operations on smaller $\alpha$-graphs. As an application of the series operation, we show that all members of a subfamily of all trees with maximum degree 4, obtained using vertex amalgamation of copies of the path $P_{11}$, are $\alpha$-graphs. We also show that the one-point union of up to four copies of $K_{n,n}$ is an ...

Potentially Eventually Positive 2-Generalized Star Sign Patterns, Yu Ber-Lin, Ting-Zhu Huang, Xu Sanzhang Apr 2019

#### Potentially Eventually Positive 2-Generalized Star Sign Patterns, Yu Ber-Lin, Ting-Zhu Huang, Xu Sanzhang

##### Electronic Journal of Linear Algebra

A sign pattern is a matrix whose entries belong to the set $\{+, -, 0\}$. An $n$-by-$n$ sign pattern $\mathcal{A}$ is said to be potentially eventually positive if there exists at least one real matrix $A$ with the same sign pattern as $\mathcal{A}$ and a positive integer $k_{0}$ such that $A^{k}>0$ for all $k\geq k_{0}$. An $n$-by-$n$ sign pattern $\mathcal{A}$ is said to be potentially eventually exponentially positive if there exists at least one real matrix $A$ with the same sign pattern as $\mathcal{A}$ and a nonnegative integer \$t_ ...

Apr 2019

#### Approximation Algorithms For Problems In Makespan Minimization On Unrelated Parallel Machines, Daniel R. Page

##### Electronic Thesis and Dissertation Repository

A fundamental problem in scheduling is makespan minimization on unrelated parallel machines (R||Cmax). Let there be a set J of jobs and a set M of parallel machines, where every job Jj ∈ J has processing time or length pi,j ∈ ℚ+ on machine Mi ∈ M. The goal in R||Cmax is to schedule the jobs non-preemptively on the machines so as to minimize the length of the schedule, the makespan. A ρ-approximation algorithm produces in polynomial time a feasible solution such that its objective value is within a multiplicative factor ρ of the optimum ...

Fractional Matching Preclusion For Butterfly Derived Networks, Xia Wang, Tianlong Ma, Chengfu Ye, Yuzhi Xiao, Fang Wang Apr 2019

#### Fractional Matching Preclusion For Butterfly Derived Networks, Xia Wang, Tianlong Ma, Chengfu Ye, Yuzhi Xiao, Fang Wang

##### Theory and Applications of Graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu [18] recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number (FMP number) of G, denoted by fmp(G), is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number (FSMP number) of G, denoted by fsmp(G), is the minimum number of vertices and edges whose deletion leaves the ...

Greatest Common Divisor: Algorithm And Proof, Mary K. Flagg Apr 2019

#### Greatest Common Divisor: Algorithm And Proof, Mary K. Flagg

##### Number Theory

No abstract provided.

Congruence Relations Mod 2 For (2 X 4^T + 1)-Colored Partitions, Nicholas Torello Apr 2019

#### Congruence Relations Mod 2 For (2 X 4^T + 1)-Colored Partitions, Nicholas Torello

##### Senior Theses

Let p_r(n) denote the difference between the number of r-colored partitions of n into an even number of distinct parts and into an odd number of distinct parts. Inspired by proofs involving modular forms of the Hirschhorn-Sellers Conjecture, we prove a similar congruence for p_r(n). Using the Jacobi Triple Product identity, we discover a much stricter congruence for p_3(n).

The Knill Graph Dimension From Clique Cover, Evatt Salinger, Dr. Kassahun Betre Mar 2019

#### The Knill Graph Dimension From Clique Cover, Evatt Salinger, Dr. Kassahun Betre

##### Seaver College Research And Scholarly Achievement Symposium

In this paper we prove that the recursive (Knill) dimension of the join of two graphs has a simple formula in terms of the dimensions of the component graphs: dim (G1 + G2) = 1 + dim G1 + dim G2. We use this formula to derive an expression for the Knill dimension of a graph from its minimum clique cover. A corollary of the formula is that a graph made of the arbitrary union of complete graphs KN of the same order KN will have dimension N − 1.

Triangle Packing On Tripartite Graphs Is Hard, Peter A. Bradshaw Mar 2019

#### Triangle Packing On Tripartite Graphs Is Hard, Peter A. Bradshaw

The problem of finding a maximum matching on a bipartite graph is well-understood and can be solved using the augmenting path algorithm. However, the similar problem of finding a large set of vertex-disjoint triangles on tripartite graphs has not received much attention. In this paper, we define a set of vertex-disjoint triangles as a “tratching.” The problem of finding a tratching that covers all vertices of a tripartite graph can be shown to be NP-complete using a reduction from the three-dimensional matching problem. In this paper, however, we introduce a new construction that allows us to emulate Boolean circuits using ...

Graphs, Random Walks, And The Tower Of Hanoi, Stephanie Egler Mar 2019

#### Graphs, Random Walks, And The Tower Of Hanoi, Stephanie Egler

The Tower of Hanoi puzzle with its disks and poles is familiar to students in mathematics and computing. Typically used as a classroom example of the important phenomenon of recursion, the puzzle has also been intensively studied its own right, using graph theory, probability, and other tools. The subject of this paper is “Hanoi graphs”, that is, graphs that portray all the possible arrangements of the puzzle, together with all the possible moves from one arrangement to another. These graphs are not only fascinating in their own right, but they shed considerable light on the nature of the puzzle itself ...

Asymptotically Optimal Bounds For (T,2) Broadcast Domination On Finite Grids, Timothy W. Randolph Mar 2019

#### Asymptotically Optimal Bounds For (T,2) Broadcast Domination On Finite Grids, Timothy W. Randolph

Let G = (V,E) be a graph and t,r be positive integers. The signal that a tower vertex T of signal strength t supplies to a vertex v is defined as sig(T, v) = max(t − dist(T,v),0), where dist(T,v) denotes the distance between the vertices v and T. In 2015 Blessing, Insko, Johnson, and Mauretour defined a (t, r) broadcast dominating set, or simply a (t, r) broadcast, on G as a set T ⊆ V such that the sum of all signal received at each vertex v ∈ V from the set of towers T ...

A Generalized Newton-Girard Identity, Tanay Wakhare Mar 2019