Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons

Open Access. Powered by Scholars. Published by Universities.®

996 Full-Text Articles 1,190 Authors 104,022 Downloads 100 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

996 full-text articles. Page 1 of 37.

On Weak Flexibility In Planar Graphs, Bernard Lidicky, Tomáš Masarík, Kyle Murphy, Shira Zerbib 2020 Iowa State University

On Weak Flexibility In Planar Graphs, Bernard Lidicky, Tomáš Masarík, Kyle Murphy, Shira Zerbib

Mathematics Publications

Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs [JGT 19']. In this new setting, each vertex v in some subset of V(G) has a request for a certain color r(v) in its list of colors L(v). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests.

The main studied question is whether there exists a universal constant ϵ>0 such that any graph G in some graph class C satisfies at least ϵ proportion of the requests. More formally, for k>0 the ...


Arithmetical Structures On Paths With A Doubled Edge, Darren B. Glass, Joshua R. Wagner 2020 Gettysburg College

Arithmetical Structures On Paths With A Doubled Edge, Darren B. Glass, Joshua R. Wagner

Math Faculty Publications

An arithmetical structure on a graph is given by a labeling of the vertices that satisfies certain divisibility properties. In this note, we look at several families of graphs and attempt to give counts on the number of arithmetical structures for graphs in these families.


Analyzing Network Topology For Ddos Mitigation Using The Abelian Sandpile Model, Bhavana Panchumarthi, Monroe Ame Stephenson 2020 Reed College

Analyzing Network Topology For Ddos Mitigation Using The Abelian Sandpile Model, Bhavana Panchumarthi, Monroe Ame Stephenson

altREU Projects

A Distributed Denial of Service (DDoS) is a cyber attack, which is capable of triggering a cascading failure in the victim network. While DDoS attacks come in different forms, their general goal is to make a network's service unavailable to its users. A common, but risky, countermeasure is to blackhole or null route the source, or the attacked destination. When a server becomes a blackhole, or referred to as the sink in the paper, the data that is assigned to it "disappears" or gets deleted. Our research shows how mathematical modeling can propose an alternative blackholing strategy that could ...


Decomposition Of Certain Complete Graphs And Complete Multipartite Graphs Into Almost-Bipartite Graphs And Bipartite Graphs, G. Sethuraman, M. Sujasree 2020 Anna University, Chennai

Decomposition Of Certain Complete Graphs And Complete Multipartite Graphs Into Almost-Bipartite Graphs And Bipartite Graphs, G. Sethuraman, M. Sujasree

Theory and Applications of Graphs

In his classical paper [14], Rosa introduced a hierarchical series of labelings called ρ, σ, β and α labeling as a tool to settle Ringel’s Conjecture which states that if T is any tree with m edges then the complete graph K2m+1 can be decomposed into 2m + 1 copies of T . Inspired by the result of Rosa [14] many researchers significantly contributed to the theory of graph decomposition using graph labeling. In this direction, in 2004, Blinco et al. [6] introduced γ-labeling as a stronger version of ρ-labeling. A function g defined on the vertex set of ...


Hadamard Diagonalizable Graphs Of Order At Most 36, Jane Breen, Steve Butler, Melissa Fuentes, Bernard Lidicky, Michael Phillips, Alexander W. N. Riasanovsky, Sung-Yell Song, Ralihe R. Villagrán, Cedar Wiseman, Xiaohong Zhang 2020 Ontario Tech University

Hadamard Diagonalizable Graphs Of Order At Most 36, Jane Breen, Steve Butler, Melissa Fuentes, Bernard Lidicky, Michael Phillips, Alexander W. N. Riasanovsky, Sung-Yell Song, Ralihe R. Villagrán, Cedar Wiseman, Xiaohong Zhang

Mathematics Publications

If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries ±1, then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable.
In this article, we prove that if n=8k+4 the only possible Hadamard diagonalizable graphs are Kn, Kn/2,n/2, 2Kn/2, and nK1, and we develop an efficient computation for determining all graphs diagonalized by a given Hadamard matrix of any order. Using these two tools, we determine and present all Hadamard diagonalizable graphs up to ...


Some Results On Seymour’S Second-Neighborhood Conjecture And On Decompositions Of Graphs, Farid Bouya 2020 Louisiana State University

Some Results On Seymour’S Second-Neighborhood Conjecture And On Decompositions Of Graphs, Farid Bouya

LSU Doctoral Dissertations

This dissertation consists of two parts. In the first part, I examine Seymour’s Second-Neighborhood Conjecture, which states that every orientation of every simple graph has at least one vertex v such that the number of vertices of out-distance 2 from v is at least as large as the number of vertices of out-distance 1 from it. I present alternative statements of this conjecture using the language of linear algebra, the last one being completely in terms of the inverse of some matrix. In the second part of this dissertation, comprising of Chapters 2 and 3, I examine two conjectures ...


Maximizing Five-Cycles In Kr-Free Graphs, Bernard Lidicky, Kyle Murphy 2020 Iowa State University

Maximizing Five-Cycles In Kr-Free Graphs, Bernard Lidicky, Kyle Murphy

Mathematics Publications

The Erdos Pentagon problem asks to find an n-vertex triangle-free graph that is maximizing the number of 5-cycles. The problem was solved using flag algebras by Grzesik and independently by Hatami, Hladky, Kral, Norin, and Razborov. Recently, Palmer suggested the general problem of maximizing the number of 5-cycles in K_{k+1}-free graphs. Using flag algebras, we show that every K_{k+1}-free graph of order n contains at most 110k4(k4−5k3+10k2−10k+4)n5+o(n5)

copies of C_5 for any k≥3, with the Turan graph begin the extremal graph for large enough n.


Laplacian Spectral Properties Of Signed Circular Caterpillars, Maurizio Brunetti 2020 University of Naples `Federico II' Italy

Laplacian Spectral Properties Of Signed Circular Caterpillars, Maurizio Brunetti

Theory and Applications of Graphs

A circular caterpillar of girth $n$ is a graph such that the removal of all pendant vertices yields a cycle $C_n$ of order $n$.

A signed graph is a pair $\Gamma=(G, \sigma)$, where $G$ is a simple graph and $\sigma: E(G) \rightarrow \{+1, -1\}$ is the sign function defined on the set $E(G)$ of edges of $G$. The signed graph $\Gamma$ is said to be balanced if the number of negatively signed edges in each cycle is even, and it is said to be unbalanced otherwise.

We determine some bounds for the first $n$ Laplacian eigenvalues of ...


Infinite Sets Of Solutions And Almost Solutions Of The Equation N∙M = Reversal(N∙M) Ii, Viorel Nitica, Cem Ekinci 2020 West Chester University of Pennsylvania

Infinite Sets Of Solutions And Almost Solutions Of The Equation N∙M = Reversal(N∙M) Ii, Viorel Nitica, Cem Ekinci

Mathematics Faculty Publications

Motivated by their intrinsic interest and by applications to the study of numeric palindromes and other sequences of integers, we discover a method for producing infinite sets of solutions and almost solutions of the equation N M reversal N M ⋅= ⋅ ( ) , our results are valid in a general numeration base b > 2 .


Graphs That Are Cospectral For The Distance Laplacian, Boris Brimkov, Ken Duna, Leslie Hogben, Kate Lorenzen, Carolyn Reinhart, Sung-Yell Song, Mark Yarrow 2020 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

Mathematics Publications

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


The Burning Number Of Directed Graphs: Bounds And Computational Complexity, Remie Janssen 2020 Delft University of Technology

The Burning Number Of Directed Graphs: Bounds And Computational Complexity, Remie Janssen

Theory and Applications of Graphs

The burning number of a graph was recently introduced by Bonato et al. Although they mention that the burning number generalizes naturally to directed graphs, no further research on this has been done. Here, we introduce graph burning for directed graphs, and we study bounds for the corresponding burning number and the hardness of finding this number. We derive sharp bounds from simple algorithms and examples. The hardness question yields more surprising results: finding the burning number of a directed tree with one indegree-0 node is NP-hard, but FPT; however, it is W[2]-complete for DAGs. Finally, we give ...


Dna Complexes Of One Bond-Edge Type, Andrew Tyler Lavengood-Ryan 2020 California State University - San Bernardino

Dna Complexes Of One Bond-Edge Type, Andrew Tyler Lavengood-Ryan

Electronic Theses, Projects, and Dissertations

DNA self-assembly is an important tool used in the building of nanostructures and targeted virotherapies. We use tools from graph theory and number theory to encode the biological process of DNA self-assembly. The principal component of this process is to examine collections of branched junction molecules, called pots, and study the types of structures that such pots can realize. In this thesis, we restrict our attention to pots which contain identical cohesive-ends, or a single bond-edge type, and we demonstrate the types and sizes of structures that can be built based on a single characteristic of the pot that is ...


Using Markov Chains To Determine Expected Propagation Time For Probabilistic Zero Forcing, Yu Chan, Emelie Curl, Jesse Geneson, Leslie Hogben, Kevin Liu, Issac Odegard, Michael S. Ross 2020 Iowa State University

Using Markov Chains To Determine Expected Propagation Time For Probabilistic Zero Forcing, Yu Chan, Emelie Curl, Jesse Geneson, Leslie Hogben, Kevin Liu, Issac Odegard, Michael S. Ross

Mathematics Publications

Zero forcing is a coloring game played on a graph where each vertex is initially colored blue or white and the goal is to color all the vertices blue by repeated use of a (deterministic) color change rule starting with as few blue vertices as possible. Probabilistic zero forcing yields a discrete dynamical system governed by a Markov chain. Since in a connected graph any one vertex can eventually color the entire graph blue using probabilistic zero forcing, the expected time to do this is studied. Given a Markov transition matrix for a probabilistic zero forcing process, an exact formula ...


Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia 2020 Balurghat College

Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia

Theory and Applications of Graphs

Radio labelling problem of graphs have their roots in communication problem known as \emph{Channel Assignment Problem}. For a simple connected graph $G=(V(G), E(G))$, a radio labeling is a mapping $f \colon V(G)\rightarrow \{0,1,2,\ldots\}$ such that $|f(u)-f(v)|\geq {\rm diam}(G)+1-d(u,v)$ for each pair of distinct vertices $u,v\in V(G)$, where $\rm{diam}(G)$ is the diameter of $G$ and $d(u,v)$ is the distance between $u$ and $v$. A radio labeling $f$ of a graph $G$ is a \emph{radio graceful labeling ...


Domination Number Of Annulus Triangulations, Toshiki Abe, Junki Higa, Shin-ichi Tokunaga 2020 Yokohama National University

Domination Number Of Annulus Triangulations, Toshiki Abe, Junki Higa, Shin-Ichi Tokunaga

Theory and Applications of Graphs

An {\em annulus triangulation} $G$ is a 2-connected plane graph with two disjoint faces $f_1$ and $f_2$ such that every face other than $f_1$ and $f_2$ are triangular, and that every vertex of $G$ is contained in the boundary cycle of $f_1$ or $f_2$. In this paper, we prove that every annulus triangulation $G$ with $t$ vertices of degree 2 has a dominating set with cardinality at most $\lfloor \frac{|V(G)|+t+1}{4} \rfloor$ if $G$ is not isomorphic to the octahedron. In particular, this bound is best possible.


Lattice Paths In Diagonals And Dimensions, Freya Bennett 2020 Coastal Carolina University

Lattice Paths In Diagonals And Dimensions, Freya Bennett

Honors Theses

The Lattice Paths of Combinatorics have been used in many applications, normally under the guise of a different name, due to its versatility in surface variety and specificity of answer. The Lattice Path’s of game development, in finding paths around barriers in mazes, is called Path Finder with the A∗ algorithms as its method of solving.


Combinatorial And Asymptotic Statistical Properties Of Partitions And Unimodal Sequences, Walter McFarland Bridges 2020 Louisiana State University and Agricultural and Mechanical College

Combinatorial And Asymptotic Statistical Properties Of Partitions And Unimodal Sequences, Walter Mcfarland Bridges

LSU Doctoral Dissertations

Our main results are asymptotic zero-one laws satisfied by the diagrams of unimodal sequences of positive integers. These diagrams consist of columns of squares in the plane; the upper boundary is called the shape. For various types of unimodal sequences, we show that, as the number of squares tends to infinity, 100% of shapes are near a certain curve---that is, there is a single limit shape. Similar phenomena have been well-studied for integer partitions, but several technical difficulties arise in the extension of such asymptotic statistical laws to unimodal sequences. We develop a widely applicable method for obtaining these limit ...


The Game Of Life On The Hyperbolic Plane, Yuncong Gu 2020 Rose-Hulman Institute of Technology

The Game Of Life On The Hyperbolic Plane, Yuncong Gu

Mathematical Sciences Technical Reports (MSTR)

In this paper, we work on the Game of Life on the hyperbolic plane. We are interested in different tessellations on the hyperbolic plane and different Game of Life rules. First, we show the exponential growth of polygons on the pentagon tessellation. Moreover, we find that the Group of 3 can keep the boundary of a set not getting smaller. We generalize the existence of still lifes by computer simulations. Also, we will prove some propositions of still lifes and cycles. There exists a still life under rules B1, B2, and S3.


Gray Codes In Music Theory, Isaac L. Vaccaro 2020 University of Maine

Gray Codes In Music Theory, Isaac L. Vaccaro

Electronic Theses and Dissertations

In the branch of Western music theory called serialism, it is desirable to construct chord progressions that use each chord in a chosen set exactly once. We view this problem through the scope of the mathematical theory of Gray codes, the notion of ordering a finite set X so that adjacent elements are related by an element of some specified set R of involutions in the permutation group of X. Using some basic results from the theory of permutation groups we translate the problem of finding Gray codes into the problem of finding Hamiltonian paths and cycles in a Schreier ...


Target Control Of Networked Systems, Isaac S. Klickstein 2020 University of New Mexico

Target Control Of Networked Systems, Isaac S. Klickstein

Mechanical Engineering ETDs

The control of complex networks is an emerging field yet it has already garnered interest from across the scientific disciplines, from robotics to sociology. It has quickly been noticed that many of the classical techniques from controls engineering, while applicable, are not as illuminating as they were for single systems of relatively small dimension. Instead, properties borrowed from graph theory provide equivalent but more practical conditions to guarantee controllability, reachability, observability, and other typical properties of interest to the controls engineer when dealing with large networked systems. This manuscript covers three topics investigated in detail by the author: (i) the ...


Digital Commons powered by bepress