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

Discrete Mathematics and Combinatorics Commons

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

956 Full-Text Articles 1,139 Authors 104,022 Downloads 101 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

956 full-text articles. Page 1 of 36.

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


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


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


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.


An Improvement In The Two-Packing Bound Related To Vizing's Conjecture, Kimber Wolff 2020 Clayton State University

An Improvement In The Two-Packing Bound Related To Vizing's Conjecture, Kimber Wolff

Theory and Applications of Graphs

Vizing's conjecture states that the domination number of the Cartesian product of graphs is at least the product of the domination numbers of the two factor graphs. In this note we improve the recent bound of Breŝar by applying a technique of Zerbib to show that for any graphs G and H, γ(G x H)≥ γ (G) 2/3(γ(H)-ρ(H)+1), where γ is the domination number, ρ is the 2-packing number, and x is the Cartesian product.


On A Vizing-Type Integer Domination Conjecture, Elliot Krop, Randy R. Davila 2020 Clayton State University

On A Vizing-Type Integer Domination Conjecture, Elliot Krop, Randy R. Davila

Theory and Applications of Graphs

Given a simple graph G, a dominating set in G is a set of vertices S such that every vertex not in S has a neighbor in S. Denote the domination number, which is the size of any minimum dominating set of G, by γ(G). For any integer k ≥ 1, a function f : V (G) → {0, 1, . . ., k} is called a {k}-dominating function if the sum of its function values over any closed neighborhood is at least k. The weight of a {k}-dominating function is the sum of its values over all the vertices. The {k}-domination ...


Recursive Formulas For Beans Functions Of Graphs, Kengo Enami, Seiya Negami 2020 Yokohama National University

Recursive Formulas For Beans Functions Of Graphs, Kengo Enami, Seiya Negami

Theory and Applications of Graphs

In this paper, we regard each edge of a connected graph $G$ as a line segment having a unit length, and focus on not only the "vertices" but also any "point" lying along such a line segment. So we can define the distance between two points on $G$ as the length of a shortest curve joining them along $G$. The beans function $B_G(x)$ of a connected graph $G$ is defined as the maximum number of points on $G$ such that any pair of points have distance at least $x>0$. We shall show a recursive formula for $B_G(x ...


On Selected Subclasses Of Matroids, Tara Elizabeth Fife 2020 Louisiana State University at Baton Rouge

On Selected Subclasses Of Matroids, Tara Elizabeth Fife

LSU Doctoral Dissertations

Matroids were introduced by Whitney to provide an abstract notion of independence.

In this work, after giving a brief survey of matroid theory, we describe structural results for various classes of matroids. A connected matroid $M$ is unbreakable if, for each of its flats $F$, the matroid $M/F$ is connected%or, equivalently, if $M^*$ has no two skew circuits. . Pfeil showed that a simple graphic matroid $M(G)$ is unbreakable exactly when $G$ is either a cycle or a complete graph. We extend this result to describe which graphs are the underlying graphs of unbreakable frame matroids. A laminar ...


Triangles In Ks-Saturated Graphs With Minimum Degree T, Craig Timmons, Benjamin Cole, Albert Curry, David Davini 2020 California State University, Sacramento

Triangles In Ks-Saturated Graphs With Minimum Degree T, Craig Timmons, Benjamin Cole, Albert Curry, David Davini

Theory and Applications of Graphs

For $n \geq 15$, we prove that the minimum number of triangles in an $n$-vertex

$K_4$-saturated graph with minimum degree 4 is exactly $2n-4$, and that there is a unique extremal

graph.

This is a triangle version of a result of

Alon, Erd\H{o}s, Holzman, and Krivelevich from 1996.

Additionally, we show that for any $s > r \geq 3$ and $t \geq 2 (s-2)+1$, there

is a $K_s$-saturated $n$-vertex graph with minimum degree $t$ that has

$\binom{ s-2}{r-1}2^{r-1} n + c_{s,r,t}$ copies of $K_r$. This shows that

unlike ...


Random Models Of Idempotent Linear Maltsev Conditions. I. Idemprimality, Clifford Bergman, Agnes Szendrei 2020 Iowa State University

Random Models Of Idempotent Linear Maltsev Conditions. I. Idemprimality, Clifford Bergman, Agnes Szendrei

Mathematics Publications

We extend a well-known theorem of Murski\v{\i} to the probability space of finite models of a system M of identities of a strong idempotent linear Maltsev condition. We characterize the models of M in a way that can be easily turned into an algorithm for producing random finite models of M, and we prove that under mild restrictions on M, a random finite model of M is almost surely idemprimal. This implies that even if such an M is distinguishable from another idempotent linear Maltsev condition by a finite model A of M, a random search for a ...


Math 220p Foundations Of Mathematics, Nicholas Vlamis 2020 CUNY Queens College

Math 220p Foundations Of Mathematics, Nicholas Vlamis

Open Educational Resources

No abstract provided.


Consecutive Prime And Highly Total Prime Labeling In Graphs, Robert Scholle 2020 La Salle University

Consecutive Prime And Highly Total Prime Labeling In Graphs, Robert Scholle

Rose-Hulman Undergraduate Mathematics Journal

This paper examines the graph-theoretical concepts of consecutive prime labeling and highly total prime labeling. These are variations on prime labeling, introduced by Tout, Dabboucy, and Howalla in 1982. Consecutive prime labeling is defined here for the first time. Consecutive prime labeling requires that the labels of vertices in a graph be relatively prime to the labels of all adjacent vertices as well as all incident edges. We show that all paths, cycles, stars, and complete graphs have a consecutive prime labeling and conjecture that all simple connected graphs have a consecutive prime labeling.

This paper also expands on work ...


Combinatorial Identities On Multinomial Coefficients And Graph Theory, Seungho Lee 2020 Montville Township High School

Combinatorial Identities On Multinomial Coefficients And Graph Theory, Seungho Lee

Rose-Hulman Undergraduate Mathematics Journal

We study combinatorial identities on multinomial coefficients. In particular, we present several new ways to count the connected labeled graphs using multinomial coefficients.


Graham's Pebbling Conjecture Holds For The Product Of A Graph And A Sufficiently Large Complete Graph, Nopparat Pleanmani 2020 Khon Kaen University

Graham's Pebbling Conjecture Holds For The Product Of A Graph And A Sufficiently Large Complete Graph, Nopparat Pleanmani

Theory and Applications of Graphs

For connected graphs $G$ and $H$, Graham conjectured that $\pi(G\square H)\leq\pi(G)\pi(H)$ where $\pi(G), \pi(H)$, and $\pi(G\square H)$ are the pebbling numbers of $G$, $H$, and the Cartesian product $G\square H$, respectively. In this paper, we show that the inequality holds when $H$ is a complete graph of sufficiently large order in terms of graph parameters of $G$.


Phylogenetic Networks And Functions That Relate Them, Drew Scalzo 2020 The University of Akron

Phylogenetic Networks And Functions That Relate Them, Drew Scalzo

Williams Honors College, Honors Research Projects

Phylogenetic Networks are defined to be simple connected graphs with exactly n labeled nodes of degree one, called leaves, and where all other unlabeled nodes have a degree of at least three. These structures assist us with analyzing ancestral history, and its close relative - phylogenetic trees - garner the same visualization, but without the graph being forced to be connected. In this paper, we examine the various characteristics of Phylogenetic Networks and functions that take these networks as inputs, and convert them to more complex or simpler structures. Furthermore, we look at the nature of functions as they relate to the ...


Discrete Morse Theory By Vector Fields: A Survey And New Directions, Matthew Nemitz 2020 Minnesota State University, Mankato

Discrete Morse Theory By Vector Fields: A Survey And New Directions, Matthew Nemitz

All Theses, Dissertations, and Other Capstone Projects

We synthesize some of the main tools in discrete Morse theory from various sources. We do this in regards to abstract simplicial complexes with an emphasis on vector fields and use this as a building block to achieve our main result which is to investigate the relationship between simplicial maps and homotopy. We use the discrete vector field as a catalyst to build a chain homotopy between chain maps induced by simplicial maps.


Digital Commons powered by bepress