Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Other Mathematics (4)
- Algebra (3)
- Applied Mathematics (3)
- Computer Sciences (3)
- Other Applied Mathematics (3)
-
- Theory and Algorithms (3)
- Life Sciences (2)
- Probability (2)
- Statistics and Probability (2)
- Artificial Intelligence and Robotics (1)
- Arts and Humanities (1)
- Biochemistry, Biophysics, and Structural Biology (1)
- Bioinformatics (1)
- Composition (1)
- Data Science (1)
- Epidemiology (1)
- Geometry and Topology (1)
- Medicine and Health Sciences (1)
- Music (1)
- Number Theory (1)
- Other Physical Sciences and Mathematics (1)
- Public Health (1)
- Set Theory (1)
- Statistical Theory (1)
- Keyword
-
- Graph theory (22)
- Domination (5)
- Coverings (4)
- Packings (4)
- Chromatic number (3)
-
- Combinatorics (3)
- Complementary prism (3)
- Covering (3)
- Design theory (3)
- Graph Theory (3)
- Combinatorial games (2)
- Decomposition (2)
- Decompositions (2)
- Double domination (2)
- Graph decomposition (2)
- Laplacian matrix (2)
- Packing (2)
- Peg solitaire (2)
- Permutation (2)
- RNA (2)
- Roman domination (2)
- Rubbling (2)
- Total domination (2)
- Triple Systems. (2)
- 1-Rotational System (1)
- 2-step domination (1)
- 3-circuit (1)
- 4-cycle (1)
- Algebra (1)
- Alliance partition (1)
- Publication Year
Articles 1 - 30 of 53
Full-Text Articles in Discrete Mathematics and Combinatorics
A Bridge Between Graph Neural Networks And Transformers: Positional Encodings As Node Embeddings, Bright Kwaku Manu
A Bridge Between Graph Neural Networks And Transformers: Positional Encodings As Node Embeddings, Bright Kwaku Manu
Electronic Theses and Dissertations
Graph Neural Networks and Transformers are very powerful frameworks for learning machine learning tasks. While they were evolved separately in diverse fields, current research has revealed some similarities and links between them. This work focuses on bridging the gap between GNNs and Transformers by offering a uniform framework that highlights their similarities and distinctions. We perform positional encodings and identify key properties that make the positional encodings node embeddings. We found that the properties of expressiveness, efficiency and interpretability were achieved in the process. We saw that it is possible to use positional encodings as node embeddings, which can be …
Roots Of Quaternionic Polynomials And Automorphisms Of Roots, Olalekan Ogunmefun
Roots Of Quaternionic Polynomials And Automorphisms Of Roots, Olalekan Ogunmefun
Electronic Theses and Dissertations
The quaternions are an extension of the complex numbers which were first described by Sir William Rowan Hamilton in 1843. In his description, he gave the equation of the multiplication of the imaginary component similar to that of complex numbers. Many mathematicians have studied the zeros of quaternionic polynomials. Prominent of these, Ivan Niven pioneered a root-finding algorithm in 1941, Gentili and Struppa proved the Fundamental Theorem of Algebra (FTA) for quaternions in 2007. This thesis finds the zeros of quaternionic polynomials using the Fundamental Theorem of Algebra. There are isolated zeros and spheres of zeros. In this thesis, we …
Partially Oriented 6-Star Decomposition Of Some Complete Mixed Graphs, Kazeem A. Kosebinu
Partially Oriented 6-Star Decomposition Of Some Complete Mixed Graphs, Kazeem A. Kosebinu
Electronic Theses and Dissertations
Let $M_v$ denotes a complete mixed graph on $v$ vertices, and let $S_6^i$ denotes the partial orientation of the 6-star with twice as many arcs as edges. In this work, we state and prove the necessary and sufficient conditions for the existence of $\lambda$-fold decomposition of a complete mixed graph into $S_6^i$ for $i\in\{1,2,3,4\}$. We used the difference method for our proof in some cases. We also give some general sufficient conditions for the existence of $S_6^i$-decomposition of the complete bipartite mixed graph for $i\in\{1,2,3,4\}$. Finally, this work introduces the decomposition of a complete mixed graph with a hole into …
Roman Domination Cover Rubbling, Nicholas Carney
Roman Domination Cover Rubbling, Nicholas Carney
Electronic Theses and Dissertations
In this thesis, we introduce Roman domination cover rubbling as an extension of domination cover rubbling. We define a parameter on a graph $G$ called the \textit{Roman domination cover rubbling number}, denoted $\rho_{R}(G)$, as the smallest number of pebbles, so that from any initial configuration of those pebbles on $G$, it is possible to obtain a configuration which is Roman dominating after some sequence of pebbling and rubbling moves. We begin by characterizing graphs $G$ having small $\rho_{R}(G)$ value. Among other things, we also obtain the Roman domination cover rubbling number for paths and give an upper bound for the …
Generalizations Of The Arcsine Distribution, Rebecca Rasnick
Generalizations Of The Arcsine Distribution, Rebecca Rasnick
Electronic Theses and Dissertations
The arcsine distribution looks at the fraction of time one player is winning in a fair coin toss game and has been studied for over a hundred years. There has been little further work on how the distribution changes when the coin tosses are not fair or when a player has already won the initial coin tosses or, equivalently, starts with a lead. This thesis will first cover a proof of the arcsine distribution. Then, we explore how the distribution changes when the coin the is unfair. Finally, we will explore the distribution when one person has won the first …
Taking Notes: Generating Twelve-Tone Music With Mathematics, Nathan Molder
Taking Notes: Generating Twelve-Tone Music With Mathematics, Nathan Molder
Electronic Theses and Dissertations
There has often been a connection between music and mathematics. The world of musical composition is full of combinations of orderings of different musical notes, each of which has different sound quality, length, and em phasis. One of the more intricate composition styles is twelve-tone music, where twelve unique notes (up to octave isomorphism) must be used before they can be repeated. In this thesis, we aim to show multiple ways in which mathematics can be used directly to compose twelve-tone musical scores.
Perfect Double Roman Domination Of Trees, Ayotunde Egunjobi
Perfect Double Roman Domination Of Trees, Ayotunde Egunjobi
Electronic Theses and Dissertations
See supplemental content for abstract
Italian Domination On Ladders And Related Products, Bradley Gardner
Italian Domination On Ladders And Related Products, Bradley Gardner
Electronic Theses and Dissertations
An Italian dominating function on a graph $G = (V,E)$ is a function such that $f : V \to \{0,1,2\}$, and for each vertex $v \in V$ for which $f(v) = 0$, we have $\sum_{u\in N(v)}f(u) \geq 2$. The weight of an Italian dominating function is $f(V) = \sum_{v\in V(G)}f(v)$. The minimum weight of all such functions on a graph $G$ is called the Italian domination number of $G$. In this thesis, we will consider Italian domination in various types of products of a graph $G$ with the complete graph $K_2$. We will find the value of the Italian domination …
The Expected Number Of Patterns In A Random Generated Permutation On [N] = {1,2,...,N}, Evelyn Fokuoh
The Expected Number Of Patterns In A Random Generated Permutation On [N] = {1,2,...,N}, Evelyn Fokuoh
Electronic Theses and Dissertations
Previous work by Flaxman (2004) and Biers-Ariel et al. (2018) focused on the number of distinct words embedded in a string of words of length n. In this thesis, we will extend this work to permutations, focusing on the maximum number of distinct permutations contained in a permutation on [n] = {1,2,...,n} and on the expected number of distinct permutations contained in a random permutation on [n]. We further considered the problem where repetition of subsequences are as a result of the occurrence of (Type A and/or Type B) replications. Our method of enumerating the Type A replications causes double …
Covering Arrays For Equivalence Classes Of Words, Joshua Cassels, Anant Godbole
Covering Arrays For Equivalence Classes Of Words, Joshua Cassels, Anant Godbole
Undergraduate Honors Theses
Covering arrays for words of length t over a d letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the dt t-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weighted sum are equivalent. In both cases we produce logarithmic upper bounds …
Vector Partitions, Jennifer French
Vector Partitions, Jennifer French
Electronic Theses and Dissertations
Integer partitions have been studied by many mathematicians over hundreds of years. Many identities exist between integer partitions, such as Euler’s discovery that every number has the same amount of partitions into distinct parts as into odd parts. These identities can be proven using methods such as conjugation or generating functions. Over the years, mathematicians have worked to expand partition identities to vectors. In 1963, M. S. Cheema proved that every vector has the same number of partitions into distinct vectors as into vectors with at least one component odd. This parallels Euler’s result for integer partitions. The primary purpose …
Vertex Weighted Spectral Clustering, Mohammad Masum
Vertex Weighted Spectral Clustering, Mohammad Masum
Electronic Theses and Dissertations
Spectral clustering is often used to partition a data set into a specified number of clusters. Both the unweighted and the vertex-weighted approaches use eigenvectors of the Laplacian matrix of a graph. Our focus is on using vertex-weighted methods to refine clustering of observations. An eigenvector corresponding with the second smallest eigenvalue of the Laplacian matrix of a graph is called a Fiedler vector. Coefficients of a Fiedler vector are used to partition vertices of a given graph into two clusters. A vertex of a graph is classified as unassociated if the Fiedler coefficient of the vertex is close to …
On T-Restricted Optimal Rubbling Of Graphs, Kyle Murphy
On T-Restricted Optimal Rubbling Of Graphs, Kyle Murphy
Electronic Theses and Dissertations
For a graph G = (V;E), a pebble distribution is defined as a mapping of the vertex set in to the integers, where each vertex begins with f(v) pebbles. A pebbling move takes two pebbles from some vertex adjacent to v and places one pebble on v. A rubbling move takes one pebble from each of two vertices that are adjacent to v and places one pebble on v. A vertex x is reachable under a pebbling distribution f if there exists some sequence of rubbling and pebbling moves that places a pebble on x. A pebbling distribution where every …
Differentiating Between A Protein And Its Decoy Using Nested Graph Models And Weighted Graph Theoretical Invariants, Hannah E. Green
Differentiating Between A Protein And Its Decoy Using Nested Graph Models And Weighted Graph Theoretical Invariants, Hannah E. Green
Electronic Theses and Dissertations
To determine the function of a protein, we must know its 3-dimensional structure, which can be difficult to ascertain. Currently, predictive models are used to determine the structure of a protein from its sequence, but these models do not always predict the correct structure. To this end we use a nested graph model along with weighted invariants to minimize the errors and improve the accuracy of a predictive model to determine if we have the correct structure for a protein.
Global Supply Sets In Graphs, Christian G. Moore
Global Supply Sets In Graphs, Christian G. Moore
Electronic Theses and Dissertations
For a graph G=(V,E), a set S⊆V is a global supply set if every vertex v∈V\S has at least one neighbor, say u, in S such that u has at least as many neighbors in S as v has in V \S. The global supply number is the minimum cardinality of a global supply set, denoted γgs (G). We introduce global supply sets and determine the global supply number for selected families of graphs. Also, we give bounds on the global supply number for general graphs, trees, and grid graphs.
The Apprentices' Tower Of Hanoi, Cory Bh Ball
The Apprentices' Tower Of Hanoi, Cory Bh Ball
Electronic Theses and Dissertations
The Apprentices' Tower of Hanoi is introduced in this thesis. Several bounds are found in regards to optimal algorithms which solve the puzzle. Graph theoretic properties of the associated state graphs are explored. A brief summary of other Tower of Hanoi variants is also presented.
Distance-2 Domatic Numbers Of Graphs, Derek Kiser
Distance-2 Domatic Numbers Of Graphs, Derek Kiser
Electronic Theses and Dissertations
The distance d(u, v) between two vertices u and v in a graph G equals the length of a shortest path from u to v. A set S of vertices is called a distance-2 dominating set if every vertex in V \S is within distance-2 of at least one vertex in S. The distance-2 domatic number is the maximum number of sets in a partition of the vertices of G into distance-2 dominating sets. We give bounds on the distance-2 domatic number of a graph and determine the distance-2 domatic number of selected classes of graphs.
A Hierarchical Graph For Nucleotide Binding Domain 2, Samuel Kakraba
A Hierarchical Graph For Nucleotide Binding Domain 2, Samuel Kakraba
Electronic Theses and Dissertations
One of the most prevalent inherited diseases is cystic fibrosis. This disease is caused by a mutation in a membrane protein, the cystic fibrosis transmembrane conductance regulator (CFTR). CFTR is known to function as a chloride channel that regulates the viscosity of mucus that lines the ducts of a number of organs. Generally, most of the prevalent mutations of CFTR are located in one of two nucleotide binding domains, namely, the nucleotide binding domain 1 (NBD1). However, some mutations in nucleotide binding domain 2 (NBD2) can equally cause cystic fibrosis. In this work, a hierarchical graph is built for NBD2. …
Permutation Groups And Puzzle Tile Configurations Of Instant Insanity Ii, Amanda N. Justus
Permutation Groups And Puzzle Tile Configurations Of Instant Insanity Ii, Amanda N. Justus
Electronic Theses and Dissertations
The manufacturer claims that there is only one solution to the puzzle Instant Insanity II. However, a recent paper shows that there are two solutions. Our goal is to find ways in which we only have one solution. We examine the permutation groups of the puzzle and use modern algebra to attempt to fix the puzzle. First, we find the permutation group for the case when there is only one empty slot at the top. We then examine the scenario when we add an extra column or an extra row to make the game a 4 × 5 puzzle or …
Very Cost Effective Domination In Graphs, Tony K. Rodriguez
Very Cost Effective Domination In Graphs, Tony K. Rodriguez
Electronic Theses and Dissertations
A set S of vertices in a graph G=(V,E) is a dominating set if every vertex in V\S is adjacent to at least one vertex in S, and the minimum cardinality of a dominating set of G is the domination number of G. A vertex v in a dominating set S is said to be very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is very cost effective if every vertex in S is very cost effective. The minimum cardinality of a very cost effective dominating set of …
Extremal Results For Peg Solitaire On Graphs, Aaron D. Gray
Extremal Results For Peg Solitaire On Graphs, Aaron D. Gray
Electronic Theses and Dissertations
In a 2011 paper by Beeler and Hoilman, the game of peg solitaire is generalized to arbitrary boards. These boards are treated as graphs in the combinatorial sense. An open problem from that paper is to determine the minimum number of edges necessary for a graph with a fixed number of vertices to be solvable. This thesis provides new bounds on this number. It also provides necessary and sufficient conditions for two families of graphs to be solvable, along with criticality results, and the maximum number of pegs that can be left in each of the two graph families.
Packings And Coverings Of Complete Graphs With A Hole With The 4-Cycle With A Pendant Edge, Yan Xia
Packings And Coverings Of Complete Graphs With A Hole With The 4-Cycle With A Pendant Edge, Yan Xia
Electronic Theses and Dissertations
In this thesis, we consider packings and coverings of various complete graphs with the 4-cycle with a pendant edge. We consider both restricted and unrestricted coverings. Necessary and sufficient conditions are given for such structures for (1) complete graphs Kv, (2) complete bipartite graphs Km,n, and (3) complete graphs with a hole K(v,w).
Very Cost Effective Partitions In Graphs, Inna Vasylieva
Very Cost Effective Partitions In Graphs, Inna Vasylieva
Electronic Theses and Dissertations
For a graph G=(V,E) and a set of vertices S, a vertex v in S is said to be very cost effective if it is adjacent to more vertices in V -S than in S.
A bipartition pi={S, V- S} is called very cost effective if both S and V- S are very cost effective sets. Not all graphs have a very cost effective bipartition, for example, the complete graphs of odd order do not. We consider several families of graphs G, including Cartesian products and cacti graphs, to determine whether G has a very cost effective bipartition.
Restricted And Unrestricted Coverings Of Complete Bipartite Graphs With Hexagons, Wesley M. Surber
Restricted And Unrestricted Coverings Of Complete Bipartite Graphs With Hexagons, Wesley M. Surber
Electronic Theses and Dissertations
A minimal covering of a graph G with isomorphic copies of graph H is a set {H1, H2, H3, ... , Hn} where Hi is isomorphic to H, the vertex set of Hi is a subset of G, the edge set of G is a subset of the union of Hi's, and the cardinality of the union of Hi's minus G is minimum. Some studies have been made of covering the complete graph in which case an added condition of the edge set of Hi …
Peg Solitaire On Trees With Diameter Four, Clayton A. Walvoort
Peg Solitaire On Trees With Diameter Four, Clayton A. Walvoort
Electronic Theses and Dissertations
In a paper by Beeler and Hoilman, the traditional game of peg solitaire is generalized to graphs in the combinatorial sense. One of the important open problems in this paper was to classify solvable trees. In this thesis, we will give necessary and sufficient conditions for the solvability for all trees with diameter four. We also give the maximum number of pegs that can be left on such a graph under the restriction that we jump whenever possible.
Cost Effective Domination In Graphs, Tabitha Lynn Mccoy
Cost Effective Domination In Graphs, Tabitha Lynn Mccoy
Electronic Theses and Dissertations
A set S of vertices in a graph G = (V,E) is a dominating set if every vertex in V \ S is adjacent to at least one vertex in S. A vertex v in a dominating set S is said to be it cost effective if it is adjacent to at least as many vertices in V \ S as it is in S. A dominating set S is cost effective if every vertex in S is cost effective. The minimum cardinality of a cost effective dominating set of G is the cost …
Global Domination Stable Graphs, Elizabeth Marie Harris
Global Domination Stable Graphs, Elizabeth Marie Harris
Electronic Theses and Dissertations
A set of vertices S in a graph G is a global dominating set (GDS) of G if S is a dominating set for both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We explore the effects of graph modifications on the global domination number. In particular, we explore edge removal, edge addition, and vertex removal.
Nested (2,R)-Regular Graphs And Their Network Properties., Josh Daniel Brooks
Nested (2,R)-Regular Graphs And Their Network Properties., Josh Daniel Brooks
Electronic Theses and Dissertations
A graph G is a (t, r)-regular graph if every collection of t independent vertices is collectively adjacent to exactly r vertices. If a graph G is (2, r)-regular where p, s, and m are positive integers, and m ≥ 2, then when n is sufficiently large, then G is isomorphic to G = Ks+mKp, where 2(p-1)+s = r. A nested (2,r)-regular graph is constructed by replacing selected cliques with a (2,r)-regular graph and joining the vertices of the peripheral cliques. For …
Preferential Arrangement Containment In Strict Superpatterns, Martha Louise Liendo
Preferential Arrangement Containment In Strict Superpatterns, Martha Louise Liendo
Electronic Theses and Dissertations
Most results on pattern containment deal more directly with pattern avoidance, or the enumeration and characterization of strings which avoid a given set of patterns. Little research has been conducted regarding the word size required for a word to contain all patterns of a given set of patterns. The set of patterns for which containment is sought in this thesis is the set of preferential arrangements of a given length. The term preferential arrangement denotes strings of characters in which repeated characters are allowed, but not necessary. Cardinalities for sets of all preferential arrangements of given lengths and alphabet sizes …
Liar's Domination In Grid Graphs, Christopher Kent Sterling
Liar's Domination In Grid Graphs, Christopher Kent Sterling
Electronic Theses and Dissertations
As introduced by Slater in 2008, liar's domination provides a way of modeling protection devices where one may be faulty. Assume each vertex of a graph G is the possible location for an intruder such as a thief. A protection device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v] and identify at which vertex in N[v] the intruder is located. A dominating set is required to identify any intruder's location in the graph G, and if any one device can fail to …