Discrete Mathematics and Combinatorics Commons^™

Congruences Of The Sums Of The First Rp Fibonacci Numbers, Tyler Warzynak

Mathematics Senior Capstone Papers

This paper serves as an extension/application of a method detailed by Chang et. al. in two separate papers which worked with sums modulo p for combinatorial sequences, positive integers r, and prime numbers p. Using a known formula, the Fibonacci numbers were converted into a sum of binomial coefficients to apply the aforementioned method. A hypothesis was formed using computational methods, where a pattern was observed to hold for the first 50,000 prime numbers. This claim was then proven following the methodology from Chang et. al. using properties of Laurent polynomials, definitions and theorems related to the Fibonacci numbers, and …

Discrete Macaulay-Steiner Geometry, Nikola Kuzmanovski

Dissertations and Doctoral Documents, University of Nebraska-Lincoln, 2023–

This thesis is concerned with discrete isoperimetric inequalities and Hilbert functions. Two generalizations of the Ahlswede-Cai local global principle are presented. These results give positive answers to two questions posed by Harper. One of these results is achieved by proving uniqueness of the lexicographic and colexicographic orders in two dimensions. The other result generalizes the technique which is commonly known as compression and includes almost all previously published results in this direction. The Ahlswede-Cai local global principle is a direct corollary of this result. Optimal downsets are studied in rectangles and triangles. All optimal downsets are found. The main result …

On Generating Bijections For Permutations And Inversion Sequences, Melanie J. Ferreri

Dartmouth College Ph.D Dissertations

Given an algebraic proof of a combinatorial identity, we use recursive methods to construct a bijection demonstrating the identity.

Our first application centers around derangements and nonderangements. A derangement is a permutation with no fixed point, and a nonderangement is a permutation with at least one fixed point. There is a one-term recurrence for the number of derangements of n elements, and we describe a bijective proof of this recurrence which can be found using a recursive map. We then show the combinatorial interpretation of this bijection and how it compares with other known bijections, and show how this extends …

Wang Tilings In Arbitrary Dimensions, Ian Tassin

Rose-Hulman Undergraduate Mathematics Journal

This paper makes a new observation about arbitrary dimensional Wang Tilings,
demonstrating that any d -dimensional tile set that can tile periodically along d − 1 axes must be able to tile periodically along all axes.
This work also summarizes work on Wang Tiles up to the present day, including
definitions for various aspects of Wang Tilings such as periodicity and the validity of a tiling. Additionally, we extend the familiar 2D definitions for Wang Tiles and associated properties into arbitrary dimensional spaces. While there has been previous discussion of arbitrary dimensional Wang Tiles in other works, it has been …

Strongly I-Bicritical Graphs, Michelle Edwards, Gary Macgillivray, Shahla Nasserasr

Theory & Applications of Graphs

A graph $G$ is \emph{strongly $i$-bicritical} if it has independent domination number $i(G) \geq 3$, and $i(G - \{x, y\}) = i(G) - 2$ whenever $x$ and $y$ are two non-adjacent vertices of $G$. We describe five constructions of strongly $i$-bicritical graphs. For four of them, necessary and sufficient conditions for the graph produced by the construction to be strongly $i$-bicritical are given. The strongly $i$-bicritical graphs with independent domination number $i(G) = 3$ are characterized, and it is shown that the strongly $i$-bicritical graphs with independent domination number $i(G) \geq 5$ may be hard to characterize. It is shown …

The Distinguishing Number Of Some Special Kind Of Graphs, Arti Salat, Amit Sharma

Applications and Applied Mathematics: An International Journal (AAM)

In the present study, the distinguishing number of some different graphs is examined where different graphs like the coconut tree graph, firecracker graph, jellyfish graph, triangular book graph, and banana tree graph have been taken into account. The major goal of the proposed study is to understand the distinguishing number of different graphs for better insights. It is evident from the results that the distinguishing numbers and automorphism groups of the above-mentioned graphs have been carried out successfully.

Some Generalizations Of Corona Product Of Two Graphs, Aparajita Borah, Gajendra Pratap Singh

Applications and Applied Mathematics: An International Journal (AAM)

In this paper we are seeking to conceptualize the notion of corona product of two graphs to contrive some special types of graphs. That is, here our attempt is to regenerate a familiar graph as a product graph. We are considering seven familiar graphs here to reconstruct them with the help of corona product of two graphs. Such types of families of the graphs and operations can be used to study biological pathways as well as to find the optimal order and size for the special types of graphs.

Optimizing Buying Strategies In Dominion, Nikolas A. Koutroulakis

Rose-Hulman Undergraduate Mathematics Journal

Dominion is a deck-building card game that simulates competing lords growing their kingdoms. Here we wish to optimize a strategy called Big Money by modeling the game as a Markov chain and utilizing the associated transition matrices to simulate the game. We provide additional analysis of a variation on this strategy known as Big Money Terminal Draw. Our results show that player's should prioritize buying provinces over improving their deck. Furthermore, we derive heuristics to guide a player's decision making for a Big Money Terminal Draw Deck. In particular, we show that buying a second Smithy is always more optimal …

Seating Groups And 'What A Coincidence!': Mathematics In The Making And How It Gets Presented, Peter J. Rowlett

Journal of Humanistic Mathematics

Mathematics is often presented as a neatly polished finished product, yet its development is messy and often full of mis-steps that could have been avoided with hindsight. An experience with a puzzle illustrates this conflict. The puzzle asks for the probability that a group of four and a group of two are seated adjacently within a hundred seats, and is solved using combinatorics techniques.

Recent Studies On The Super Edge-Magic Deficiency Of Graphs, Rikio Ichishima, Susana C. Lopez, Francesc Muntaner, Yukio Takahashi

Theory & Applications of Graphs

A graph $G$ is called edge-magic if there exists a bijective function $f:V\left(G\right) \cup E\left(G\right)\rightarrow \left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert +\left\vert E\left(G\right) \right\vert \right\}$ such that $f\left(u\right) + f\left(v\right) + f\left(uv\right)$ is a constant for each $uv\in E\left( G\right) $. Also, $G$ is called super edge-magic if $f\left(V \left(G\right)\right) =\left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}$. Furthermore, the super edge-magic deficiency $ \mu_{s}\left(G\right)$ of a graph $G$ is defined to be either the smallest nonnegative integer $n$ with the property that $G \cup nK_{1}$ is super edge-magic or $+ \infty$ if there exists no such …

A Survey Of Maximal K-Degenerate Graphs And K-Trees, Allan Bickle

Theory & Applications of Graphs

This article surveys results on maximal $k$-degenerate graphs, $k$-trees,

and related classes including simple $k$-trees, $k$-paths, maximal

outerplanar graphs, and Apollonian networks. These graphs are important

in many problems in graph theory and computer science. Types of results

surveyed include structural characterizations, enumeration, degree

sets and sequences, chromatic polynomials, algorithms, and related

extremal problems.

On The Singular Pebbling Number Of A Graph, Harmony R. Morris

Rose-Hulman Undergraduate Mathematics Journal

In this paper, we define a new parameter of a connected graph as a spin-off of the pebbling number (which is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble). This new parameter is the singular pebbling number, the smallest t such that a player can be given any configuration of at least t pebbles and any target vertex and can successfully move pebbles so that exactly one pebble ends on the target vertex. We also prove that the singular pebbling number of any graph on 3 or more vertices is equal …

The Dual Boundary Complex Of The Moduli Space Of Cyclic Compactifications, Toby Anderson

HMC Senior Theses

Moduli spaces provide a useful method for studying families of mathematical objects. We study certain moduli spaces of algebraic curves, which are generalizations of familiar lines and conics. This thesis focuses on, Δ^(r,n), the dual boundary complex of the moduli space of genus-zero cyclic curves. This complex is itself a moduli space of graphs and can be investigated with combinatorial methods. Remarkably, the combinatorics of this complex provides insight into the geometry and topology of the original moduli space. In this thesis, we investigate two topologically invariant properties of Δ^(r,n). We compute its Euler characteristic and …

Solid Angle Measure Approximation Methods For Polyhedral Cones, Allison Fitisone

Theses and Dissertations--Mathematics

Polyhedral cones are of interest in many fields, like geometry and optimization. A simple, yet fundamental question we may ask about a cone is how large it is. As cones are unbounded, we consider their solid angle measure: the proportion of space that they occupy. Beyond dimension three, definitive formulas for this measure are unknown. Consequently, devising methods to estimate this quantity is imperative. In this dissertation, we endeavor to enhance our understanding of solid angle measures and provide valuable insights into the efficacy of various approximation techniques.

Ribando and Aomoto independently discovered a Taylor series formula for solid angle …

An Approach To Multidimensional Discrete Generating Series, Svetlana S. Akhtamova, Tom Cuchta, Alexander P. Lyapin

Mathematics Faculty Research

We extend existing functional relationships for the discrete generating series associated with a single-variable linear polynomial coefficient difference equation to the multivariable case.

Enumeration Of Increasing Trees, Garrett M. Southwood

Honors College Theses

We consider the generating function for increasingly labelled trees. By generalizing the proof through symbolic method, we are able to study various statistics regarding binary increasing trees with respect to height restrictions. We then apply our approach to special colorings of increasing trees in order to obtain their generating functions and, from there, derive the counting sequence for (ak+a)-colored recursive trees. We also present some interesting bijections between colored and non-colored increasing trees.

Slₖ-Tilings And Paths In ℤᵏ, Zachery T. Peterson

Theses and Dissertations--Mathematics

An SLₖ-frieze is a bi-infinite array of integers where adjacent entries satisfy a certain diamond rule. SL₂-friezes were introduced and studied by Conway and Coxeter. Later, these were generalized to infinite matrix-like structures called tilings as well as higher values of k. A recent paper by Short showed a bijection between bi-infinite paths of reduced rationals in the Farey graph and SL₂-tilings. We extend this result to higher k by constructing a bijection between SLₖ-tilings and certain pairs of bi-infinite strips of vectors in ℤᵏ called paths. The key ingredient in the proof is the relation to Plucker friezes and …

On Graph Decompositions And Designs: Exploring The Hamilton-Waterloo Problem With A Factor Of 6-Cycles And Projective Planes Of Order 16, Zazil Santizo Huerta

Dissertations, Master's Theses and Master's Reports

This dissertation tackles the challenging graph decomposition problem of finding solutions to the uniform case of the Hamilton-Waterloo Problem (HWP). The HWP seeks decompositions of complete graphs into cycles of specific lengths. Here, we focus on cases with a single factor of 6-cycles. The dissertation then delves into the construction of 1-rotational designs, a concept from finite geometry. It explores the connection between these designs and finite projective planes, which are specific geometric structures. Finally, the dissertation proposes a potential link between these seemingly separate areas. It suggests investigating whether 1-rotational designs might hold the key to solving unsolved instances …

Optimal Network Analysis Through Vertex Order Coloring Of Intuitionistic Fuzzy Graph Operations, A. Meenakshi, S. Dhanushiya, Hong Qin, Maniyandy Elangovan

Data Science Faculty Publications

Intuitionistic fuzzy graphs IFGs are a powerful tool for modeling uncertainty and complex relationships. They offer versatile frameworks for addressing real-world challenges. In this research, we have introduced intuitionistic fuzzy vertex order coloring IFVOC and analyzed the alpha-strong (alpha str), beta-strong (beta str), and gamma-strong (gamma str) vertices through their degree. We explored important theorems based on the types of strong vertices, broadening the scope of our study. We analyzed multiple IFG products to determine the most optimal network based on some important metrics, including the weight and total number of alpha str vertices, the chromatic number, and the weight …

Id Numbers Of Lobster Graphs, Mark Anthony C. Tolentino, Luis Silvestre Jr, Richwell T. Chan Sim, Amir Jann Erikson Diga, Althea Julia R. Loyola

Mathematics Faculty Publications

No abstract provided.

On The Structure Of Repeated-Root Polycyclic Codes Over Local Rings, Maryam Bajalan, Edgar Martinez-Moro, Reza Sobhani, Steve Szabo, Guelsuem Goezde Yilmazguc

EKU Faculty and Staff Scholarship

This paper provides the Generalized Mattson Solomon polynomial for repeated-root polycyclic codes over local rings that gives an explicit decomposition of them in terms of idempotents. It also states some structural properties of repeated-root polycyclic codes over finite fields in terms of matrix product codes. Both approaches provide a description of the perpendicular to 0-dual code for a given polycyclic code. (c) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Paley Graphs, Prime Graphs, And Crossword Puzzles, Robert D. Jacobs Jr.

Theses and Dissertations

In this paper, we will talk about many different mathematical concepts. We will prove theorems about Paley graphs, prime graphs, and crossword puzzles. It will be very fun.

The results in the section about Paley graphs include structure theorems about the subgraph induced by the quadratic residues, the subgraph induced by the non-residues and a few related subgraphs. The main is to better understand the “independence structure” of the Paley graph itself. No good upper bound on the independence number of Paley graphs is known. Theorems about these subgraphs, and various counts aim at future improvement of upper bounds for …

Problems In Graph Theory With Applications To Topology And Modeling Rna, Rayan K. Ibrahim

Theses and Dissertations

In this thesis, we explore four projects. In the first project, we explore $r$-neighbor bootstrap percolation on a graph $G$. We establish upper bounds for the number of vertices required to percolate in the case that $r=2$ for particular classes of graphs. In the second project, we study the structure of graphs with independence number two. We prove a lower bound on the number of edges of such graphs, related to an upper bound on the number of edges in a triangle-saturated graph, and give a sufficient forbidden induced subgraph condition for independence number two graphs. In the third project, …

Graph Coloring Reconfiguration, Reem Mahmoud

Theses and Dissertations

Reconfiguration is the concept of moving between different solutions to a problem by transforming one solution into another using some prescribed transformation rule (move). Given two solutions s₁ and s₂ of a problem, reconfiguration asks whether there exists a sequence of moves which transforms s₁ into s₂. Reconfiguration is an area of research with many contributions towards various fields such as mathematics and computer science.
The k-coloring reconfiguration problem asks whether there exists a sequence of moves which transforms one k-coloring of a graph G into another. A move in this case is a type …

Multicolor Bipartite Ramsey Number Of Double Stars, Gregory M. Decamillis

Honors Undergraduate Theses

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. For positive integers $n, m$, the double star $S(n,m)$ is the graph consisting of the disjoint union of two stars $K_{1,n}$ and $K_{1,m}$ together with an edge joining their centers. The $k$-color bipartite Ramsey number of $ S(n,m)$, denoted by $r_{bip}(S(n,m);k)$, is the smallest integer $N$ such that, in any $k$-coloring of the edges of the complete bipartite graph $K_{N,N}$, there is a monochromatic copy …

Recoloring In Hereditary Graph Classes: Structure And Decomposition, Manoj Belavadi

Theses and Dissertations (Comprehensive)

In this thesis we study reconfiguration problems in graph theory. A reconfiguration problem is generally defined on the solution space of a problem for which a configuration can be defined as a feasible solution, for example, a coloring of a graph. In Chapters 1 through 4 we study the reconfiguration of vertex colorings. The reconfiguration graph of the k-colorings, denoted R_k(G), is the graph whose vertices are the k-colorings of G and two colorings are adjacent in R_k(G) if they differ on exactly one vertex. The basic question investigated here …

Problems In Chemical Graph Theory Related To The Merrifield-Simmons And Hosoya Topological Indices, William B. O'Reilly

College of Graduate Studies: Theses & Dissertations

In some sense, chemical graph theory applies graph theory to various physical sciences. This interdisciplinary field has significant applications to structure property relationships, as well as mathematical modeling. In particular, we focus on two important indices widely used in chemical graph theory, the Merrifield-Simmons index and Hosoya index. The Merrifield-Simmons index and the Hosoya index are two well-known topological indices used in mathematical chemistry for characterizing specific properties of chemical compounds. Substantial research has been done on the two indices in terms of enumerative problems and extremal questions. In this thesis, we survey known extremal results and consider the generalized …

Enumeration Of Lattice Paths With Restrictions, Vince White

College of Graduate Studies: Theses & Dissertations

Lattice path enumeration, through the lens of Catalan numbers, plays a crucial role in combinatorics. This thesis delves into enumerations of some of the most common lattice paths – north-east paths, up-down paths, and Dyck paths – with restrictions applied. The first restriction is counting north-east lattice paths that only cross the diagonal line, y=x, once. The second form of lattice paths with restrictions is up-down paths that cross the x-axis exactly once and fall to a fixed depth of k. While working through this module, a novel proof for a known integer sequence was used, then applied to generate …

Counting Conjugates Of Colored Compositions, Jesus Omar Sistos Barron

Honors College Theses

The properties of n-color compositions have been studied parallel to those of regular compositions. The conjugate of a composition as defined by MacMahon, however, does not translate well to n-color compositions, and there is currently no established analogous concept. We propose a conjugation rule for cyclic n-color compositions. We also count the number of self-conjugates under these rules and establish a couple of connections between these and regular compositions.

Zeckendorf Representation Analysis On Third Order Fibonacci Sequences That Do Not Satisfy The Uniqueness Property, Samuel A. Aguilar

Honors College Theses

Zeckendorf's Theorem states that every natural number can be expressed uniquely as the sum of distinct non-consecutive terms of the shifted Fibonacci sequence (i.e. 1, 2, 3, 5, ...). This theorem has motivated the study of representation of integers by the sum of non-adjacent terms of Nth order Fibonacci sequences, including the characterization of the uniqueness of Zeckendorf representation based on the initial terms of the sequence. Moreover, when this uniqueness property is satisfied for third order Fibonacci sequences, the ratio of integers less than a given number X that have a Zeckendorf representation has been estimated by Dr. Sungkon …