Discrete Mathematics and Combinatorics Commons™

All Articles in Discrete Mathematics and Combinatorics

977 full-text articles. Page 1 of 37.

Coloring Count Cones Of Planar Graphs, 2019 Charles University, Prague

Coloring Count Cones Of Planar Graphs, Zdenek Dvorak, Bernard Lidicky

Mathematics Publications

For a plane near-triangulation G with the outer face bounded by a cycle C, let n⋆G denote the function that to each 4-coloring ψ of C assigns the number of ways ψ extends to a 4-coloring of G. The block-count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function n⋆G belongs to a certain cone in the space of all functions from 4-colorings of C to real numbers. We investigate the properties of this cone for |C|=5, formulate a conjecture strengthening the ...

Non-Sparse Companion Matrices, 2019 Redeemer University College

Non-Sparse Companion Matrices, Louis Deaett, Jonathan Fischer, Colin Garnett, Kevin N. Vander Meulen

Electronic Journal of Linear Algebra

Given a polynomial $p(z)$, a companion matrix can be thought of as a simple template for placing the coefficients of $p(z)$ in a matrix such that the characteristic polynomial is $p(z)$. The Frobenius companion and the more recently-discovered Fiedler companion matrices are examples. Both the Frobenius and Fiedler companion matrices have the maximum possible number of zero entries, and in that sense are sparse. In this paper, companion matrices are explored that are not sparse. Some constructions of non-sparse companion matrices are provided, and properties that all companion matrices must exhibit are given. For example, it is ...

List-Distinguishing Cartesian Products Of Cliques, 2019 University of Colorado, Denver

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 Mystery Of Frobenius Symmetry, 2019 DePaul University

The Mystery Of Frobenius Symmetry, Maciej Piwowarczyk

DePaul Discoveries

In this project we studied the mathematical concept of the Frobenius number and some curious patterns that come with it. One common example of the Frobenius number is the Coin Problem: If handed two denominations of coins, say 4¢ and 5¢, and asked to create all possible values, we will eventually find ourselves in a position where we can make any value. With 4¢ and 5¢ coins, we can create any value above 11¢, but not 11¢ itself. So, that makes 11 the Frobenius number of 4 and 5. What we explore in this paper is a pattern we call ...

Pascal's Triangle, Pascal's Pyramid, And The Trinomial Triangle, 2019 California State University, San Bernardino

Pascal's Triangle, Pascal's Pyramid, And The Trinomial Triangle, Antonio Saucedo Jr.

Electronic Theses, Projects, and Dissertations

Many properties have been found hidden in Pascal's triangle. In this paper, we will present several known properties in Pascal's triangle as well as the properties that lift to different extensions of the triangle, namely Pascal's pyramid and the trinomial triangle. We will tailor our interest towards Fermat numbers and the hockey stick property. We will also show the importance of the hockey stick properties by using them to prove a property in the trinomial triangle.

2019 California State University - San Bernardino

Analogues Between Leibniz's Harmonic Triangle And Pascal's Arithmetic Triangle, Lacey Taylor James

Electronic Theses, Projects, and Dissertations

This paper will discuss the analogues between Leibniz's Harmonic Triangle and Pascal's Arithmetic Triangle by utilizing mathematical proving techniques like partial sums, committees, telescoping, mathematical induction and applying George Polya's perspective. The topics presented in this paper will show that Pascal's triangle and Leibniz's triangle both have hockey stick type patterns, patterns of sums within shapes, and have the natural numbers, triangular numbers, tetrahedral numbers, and pentatope numbers hidden within. In addition, this paper will show how Pascal's Arithmetic Triangle can be used to construct Leibniz's Harmonic Triangle and show how both triangles ...

Recent Trends In Combinatorics, 2019 Macalester College

Recent Trends In Combinatorics, Andrew Beveridge, Jerrold R. Griggs, Leslie Hogben, Gregg Musiker, Prasad Tetali

Leslie Hogben

Section 1: Extremal and Probabilistic Combinatorics -- Problems Related to Graph Indices in Trees -- The edit distance in graphs: methods, results and generalizations -- Repetitions in graphs and sequences -- On Some Extremal Problems for Cycles in Graphs -- A survey of Turan problems for expansions -- Survey on matching, packing and Hamilton cycle problems on hypergraphs -- Rainbow Hamilton cycles in random graphs and hypergraphs -- Further applications of the Container Method -- Independent transversals and hypergraph matchings - an elementary approach -- Giant components in random graphs -- Infinite random graphs and properties of metrics -- Nordhaus-Gaddum Problems for Colin de Verdière Type Parameters, Variants of Tree-width, and Related Parameters ...

Nonstandard Dice That Both Count For Card Craps, 2019 University of Nevada, Las Vegas

Nonstandard Dice That Both Count For Card Craps, Mark Bollman

International Conference on Gambling & Risk Taking

The Pala Casino in California deals Card Craps using a red die numbered {2; 2; 2; 5; 5; 5} and a blue die numbered {3; 3; 3; 4; 4; 4}. Two cards from a special 36-card deck, which contains one card bearing each of the 36 ways in which two dice can land when rolled, are dealt: one each face down to a red space and a blue space. When the dice are rolled, the higher number determines which of the cards is flipped over.

A moment's reflection reveals that Pala's blue die is unnecessary. The card selection ...

Minimum Rank, Maximum Nullity, And Zero Forcing Number Of Graphs, 2019 University of Regina

Minimum Rank, Maximum Nullity, And Zero Forcing Number Of Graphs, Shaun M. Fallat, Leslie Hogben

Leslie Hogben

This chapter represents an overview of research related to a notion of the “rank of a graph" and the dual concept known as the “nullity of a graph," from the point of view of associating a fixed collection of symmetric or Hermitian matrices to a given graph. This topic and related questions have enjoyed a fairly large history within discrete mathematics, and have become very popular among linear algebraists recently, partly based on its connection to certain inverse eigenvalue problems, but also because of the many interesting applications (e.g., to communication complexity in computer science and to control of ...

The Determinant Of A Complex Matrix And Gershgorin Circles, 2019 Hamburg University of Technology

The Determinant Of A Complex Matrix And Gershgorin Circles, Florian Bünger, Siegfried M. Rump

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, 2019 University of Texas at Tyler

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, 2019 Merrimack College

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.

Vertex And Edge Spread Of Zero Forcing Number, Maximum Nullity, And Minimum Rank Of A Graph, 2019 Willamette University

Vertex And Edge Spread Of Zero Forcing Number, Maximum Nullity, And Minimum Rank Of A Graph, Christina J. Edholm, Leslie Hogben, My Huynh, Josh Lagrange, Darren D. Row

Leslie Hogben

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i not equal j) is nonzero whenever {i, j} is an edge in G and is zero otherwise; maximum nullity is taken over the same set of matrices. The zero forcing number is the minimum size of a zero forcing set of vertices and bounds the maximum nullity from above. The spread of a graph parameter at a vertex v or edge e of G is the difference between the value of the parameter on ...

Maximum Oriented Forcing Number For Complete Graphs, 2019 University of Haifa-Oranim

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, 2019 Iowa State University

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, 2019 Iowa State University and American Institute of Mathematics

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 ...

Cop Throttling Number: Bounds, Values, And Variants, 2019 Ryerson University

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 ...

Graphs That Are Cospectral For The Distance Laplacian, 2019 Rice University

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 ...

2019 Iowa State University

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, 2019 Iowa State University

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 ...