# Discrete Mathematics and Combinatorics Commons™

## All Articles in Discrete Mathematics and Combinatorics

865 full-text articles. Page 6 of 31.

Extensions Of The Morse-Hedlund Theorem, 2018 Bucknell University

#### Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell

##### Honors Theses

Bi-infinite words are sequences of characters that are infinite forwards and backwards; for example "...ababababab...". The Morse-Hedlund theorem says that a bi-infinite word f repeats itself, in at most n letters, if and only if the number of distinct subwords of length n is at most n. Using the example, "...ababababab...", there are 2 subwords of length 3, namely "aba" and "bab". Since 2 is less than 3, we must have that "...ababababab..." repeats itself after at most 3 letters. In fact it does repeat itself every two letters. Interestingly, there are many extensions of this theorem to multiple dimensions ...

2018 Georgia Southern University

#### A General Lower Bound On Gallai-Ramsey Numbers For Non-Bipartite Graphs, Colton Magnant

##### Theory and Applications of Graphs

Given a graph $H$ and a positive integer $k$, the $k$-color Gallai-Ramsey number $gr_{k}(K_{3} : H)$ is defined to be the minimum number of vertices $n$ for which any $k$-coloring of the complete graph $K_{n}$ contains either a rainbow triangle or a monochromatic copy of $H$. The behavior of these numbers is rather well understood when $H$ is bipartite but when $H$ is not bipartite, this behavior is a bit more complicated. In this short note, we improve upon existing lower bounds for non-bipartite graphs $H$ to a value that we conjecture to be sharp ...

Generalized Matching Preclusion In Bipartite Graphs, 2018 Oakland University

#### Generalized Matching Preclusion In Bipartite Graphs, Zachary Wheeler, Eddie Cheng, Dana Ferranti, Laszlo Liptak, Karthik Nataraj

##### 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 that has no perfect matchings. For many interconnection networks, the optimal such sets are precisely sets of edges incident to a single vertex. The conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond these, and it is defined as the minimum number of edges whose deletion results in a graph with neither isolated vertices nor perfect matchings. In this paper we generalize this concept to get a hierarchy of ...

Zero Forcing And Power Domination For Graph Products, 2018 Westminster College - Fulton

#### Zero Forcing And Power Domination For Graph Products, Katherine F. Benson, Daniela Ferrero, Mary Flagg, Veronika Furst, Leslie Hogben, Violeta Vasilevska, Brian Wissman

##### Mathematics Publications

The power domination number arose from the monitoring of electrical networks, and methods for its determination have the associated application. The zero forcing number arose in the study of maximum nullity among symmetric matrices described by a graph (and also in control of quantum systems and in graph search algorithms). There has been considerable effort devoted to the determination of the power domination number, the zero forcing number, and maximum nullity for specific families of graphs. In this paper we exploit the natural relationship between power domination and zero forcing to obtain results for the power domination number of tensor ...

The Relationship Between K-Forcing And K-Power Domination, 2018 Texas State University

#### The Relationship Between K-Forcing And K-Power Domination, Daniela Ferrero, Leslie Hogben, Franklin H.J. Kenter, Michael Young

##### Mathematics Publications

Zero forcing and power domination are iterative processes on graphs where an initial set of vertices are observed, and additional vertices become observed based on some rules. In both cases, the goal is to eventually observe the entire graph using the fewest number of initial vertices. The concept of k-power domination was introduced by Chang et al. (2012) as a generalization of power domination and standard graph domination. Independently, k-forcing was defined by Amos et al. (2015) to generalize zero forcing. In this paper, we combine the study of k-forcing and k-power domination, providing a new approach to analyze both ...

Applications Of Analysis To The Determination Of The Minimum Number Of Distinct Eigenvalues Of A Graph, 2018 Iowa State University

#### Applications Of Analysis To The Determination Of The Minimum Number Of Distinct Eigenvalues Of A Graph, Beth Bjorkman, Leslie Hogben, Scarlitte Ponce, Carolyn Reinhart, Theodore Tranel

##### Mathematics Publications

We establish new bounds on the minimum number of distinct eigenvalues among real symmetric matrices with nonzero off-diagonal pattern described by the edges of a graph and apply these to determine the minimum number of distinct eigenvalues of several families of graphs and small graphs.

Polychromatic Colorings On The Hypercube, 2018 West Virginia University

#### Polychromatic Colorings On The Hypercube, John Goldwasser, Bernard Lidicky, Ryan R. Martin, David Offner, John Talbot, Michael Young

##### Mathematics Publications

Given a subgraph G of the hypercube Qn, a coloring of the edges of Qn such that every embedding of G contains an edge of every color is called a G-polychromatic coloring. The maximum number of colors with which it is possible to G-polychromatically color the edges of any hypercube is called the polychromatic number of G. To determine polychromatic numbers, it is only necessary to consider a specific type of coloring, which we call simple. The main tool for finding upper bounds on polychromatic numbers is to translate the question of polychromatically coloring the hypercube so every embedding of ...

Fine Structure Of 4-Critical Triangle-Free Graphs Iii. General Surfaces, 2018 Charles University, Prague

#### Fine Structure Of 4-Critical Triangle-Free Graphs Iii. General Surfaces, Zdenek Dvorak, Bernard Lidicky

##### Mathematics Publications

Dvořák, Král', and Thomas [Three-Coloring Triangle-Free Graphs on Surfaces IV. Bounding Face Sizes of 4-Critical Graphs, preprint, arXiv:1404.6356v3, 2015; Three-Coloring Triangle-Free Graphs on Surfaces VI. 3-Colorability of Quadrangulations, preprint, arXiv:1509.01013, 2015] gave a description of the structure of triangle-free graphs on surfaces with respect to 3-coloring. Their description, however, contains two substructures (both related to graphs embedded in a plane with two precolored cycles) whose coloring properties are not entirely determined. In this paper, we fill these gaps.

On The Strong Chromatic Index Of Sparse Graphs, 2018 Westfield State University

#### On The Strong Chromatic Index Of Sparse Graphs, Philip Deorsey, Michael Ferrara, Nathan Graber, Stephen G. Hartke, Luke L. Nelsen, Eric Sullivan, Sogol Jahanbekam, Bernard Lidicky, Derrick Stolee, Jennifer White

##### Mathematics Publications

The strong chromatic index of a graph G, denoted χ′s(G), is the least number of colors needed to edge-color G so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted χ′s,ℓ(G), is the least integer k such that if arbitrary lists of size k are assigned to each edge then G can be edge-colored from those lists where edges at distance at most two receive distinct colors.

We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if G is a subcubic planar graph with ...

Pbw Bases And Marginally Large Tableaux In Type D, 2018 Central Michigan University

#### Pbw Bases And Marginally Large Tableaux In Type D, Ben Salisbury, Adam Schultze, Peter Tingley

##### Mathematics and Statistics: Faculty Publications and Other Works

We give an explicit description of the unique crystal isomorphism between two realizations of B(∞) in type D: that using marginally large tableaux and that using PBW monomials with respect to one particularly nice reduced expression of the longest word

A Survey On Monochromatic Connections Of Graphs, 2018 Nankai University

#### A Survey On Monochromatic Connections Of Graphs, Xueliang Li, Di Wu

##### Theory and Applications of Graphs

The concept of monochromatic connection of graphs was introduced by Caro and Yuster in 2011. Recently, a lot of results have been published about it.
In this survey, we attempt to bring together all the results that dealt with it.
We begin with an introduction, and then classify the results into the following categories: monochromatic connection coloring of edge-version, monochromatic connection coloring of vertex-version, monochromatic index, monochromatic connection coloring of total-version.

2018 University of Kentucky

#### Hilbert Bases, Descent Statistics, And Combinatorial Semigroup Algebras, Mccabe J. Olsen

##### Theses and Dissertations--Mathematics

The broad topic of this dissertation is the study of algebraic structure arising from polyhedral geometric objects. There are three distinct topics covered over three main chapters. However, each of these topics are further linked by a connection to the Eulerian polynomials.

Chapter 2 studies Euler-Mahonian identities arising from both the symmetric group and generalized permutation groups. Specifically, we study the algebraic structure of unit cube semigroup algebra using Gröbner basis methods to acquire these identities. Moreover, this serves as a bridge between previous methods involving polyhedral geometry and triangulations with descent bases methods arising in representation theory.

In Chapter ...

Polytopes Associated To Graph Laplacians, 2018 University of Kentucky

#### Polytopes Associated To Graph Laplacians, Marie Meyer

##### Theses and Dissertations--Mathematics

Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, PG, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, PD.

Basic properties of both families of simplices, PG and PD, are established using techniques ...

2018 Georgia Southern University

#### Sparse Trees With A Given Degree Sequence, Ao Shen

##### Electronic Theses and Dissertations

In this thesis, we consider the properties of sparse trees and summarized a certain class of trees under some constraint (including with a given degree sequence, with given number of leaves, with given maximum degree, etc.) which have maximum Wiener index and the minimum number of subtrees at the same time. Wiener index is one of the most important topological indices in chemical graph theory. Steiner k􀀀 Wiener index can be regarded as the generalization of Wiener index, when k = 2, Steiner Wiener index is the same as Wiener index. Steiner k􀀀 Wiener index of a tree T is the ...

Notes On The Proof Of The Van Der Waerden Permanent Conjecture, 2018 Iowa State University

#### Notes On The Proof Of The Van Der Waerden Permanent Conjecture, Vicente Valle Martinez

##### Creative Components

The permanent of an $n\times n$ matrix $A=(a_{i j})$ with real entries is defined by the sum $$\sum_{\sigma \in S_n} \prod_{i=1}^{n} a_{i \sigma(i)}$$ where $S_n$ denotes the symmetric group on the $n$-element set $\{1,2,\dots,n\}$. In this creative component we survey some known properties of permanents, calculation of permanents for particular types of matrices and their applications in combinatorics and linear algebra. Then we follow the lines of van Lint's exposition of Egorychev's proof for the van der Waerden's conjecture on the permanents of doubly ...

An Incidence Approach To The Distinct Distances Problem, 2018 Claremont Colleges