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 31 - 53 of 53
Full-Text Articles in Discrete Mathematics and Combinatorics
Omnisculptures., Cihan Eroglu
Omnisculptures., Cihan Eroglu
Electronic Theses and Dissertations
In this thesis we will study conditions for the existence of minimal sized omnipatterns in higher dimensions. We will introduce recent work conducted on one dimensional and two dimensional patterns known as omnisequences and omnimosaics, respectively. These have been studied by Abraham et al [3] and Banks et al [2]. The three dimensional patterns we study are called omnisculptures, and will be the focus of this thesis. A (K,a) omnisequence of length n is a string of letters that contains each of the ak words of length k over [A]={1,2,...a} as a substring. …
Universal Hypergraphs., Michael Deren
Universal Hypergraphs., Michael Deren
Electronic Theses and Dissertations
In this thesis, we study universal hypergraphs. What are these? Let us start with defining a universal graph as a graph on n vertices that contains each of the many possible graphs of a smaller size k < n as an induced subgraph. A hypergraph is a discrete structure on n vertices in which edges can be of any size, unlike graphs, where the edge size is always two. If all edges are of size three, then the hypergraph is said to be 3-uniform. If a 3-uniform hypergraph can have edges colored one of a colors, then it is called a …
A Predictive Model Which Uses Descriptors Of Rna Secondary Structures Derived From Graph Theory., Alissa Ann Rockney
A Predictive Model Which Uses Descriptors Of Rna Secondary Structures Derived From Graph Theory., Alissa Ann Rockney
Electronic Theses and Dissertations
The secondary structures of ribonucleic acid (RNA) have been successfully modeled with graph-theoretic structures. Often, simple graphs are used to represent secondary RNA structures; however, in this research, a multigraph representation of RNA is used, in which vertices represent stems and edges represent the internal motifs. Any type of RNA secondary structure may be represented by a graph in this manner. We define novel graphical invariants to quantify the multigraphs and obtain characteristic descriptors of the secondary structures. These descriptors are used to train an artificial neural network (ANN) to recognize the characteristics of secondary RNA structure. Using the ANN, …
Total Domination Dot Critical And Dot Stable Graphs., Stephanie Anne Marie Mcmahon
Total Domination Dot Critical And Dot Stable Graphs., Stephanie Anne Marie Mcmahon
Electronic Theses and Dissertations
Two vertices are said to be identifed if they are combined to form one vertex whose neighborhood is the union of their neighborhoods. A graph is total domination dot-critical if identifying any pair of adjacent vertices decreases the total domination number. On the other hand, a graph is total domination dot-stable if identifying any pair of adjacent vertices leaves the total domination number unchanged. Identifying any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most two. Among other results, we characterize total domination dot-critical trees with total …
A Predictive Model For Secondary Rna Structure Using Graph Theory And A Neural Network., Denise Renee Koessler
A Predictive Model For Secondary Rna Structure Using Graph Theory And A Neural Network., Denise Renee Koessler
Electronic Theses and Dissertations
In this work we use a graph-theoretic representation of secondary RNA structure found in the database RAG: RNA-As-Graphs. We model the bonding of two RNA secondary structures to form a larger structure with a graph operation called merge. The resulting data from each tree merge operation is summarized and represented by a vector. We use these vectors as input values for a neural network and train the network to recognize a tree as RNA-like or not based on the merge data vector.
The network correctly assigned a high probability of RNA-likeness to trees identified as RNA-like in the RAG database, …
The Last Of The Mixed Triple Systems., Ernest Jum
The Last Of The Mixed Triple Systems., Ernest Jum
Electronic Theses and Dissertations
In this thesis, we consider the decomposition of the complete mixed graph on v vertices denoted Mv, into every possible mixed graph on three vertices which has (like Mv) twice as many arcs as edges. Direct constructions are given in most cases. Decompositions of theλ-fold complete mixed graph λMv, are also studied.
Independent Domination In Complementary Prisms., Joel Agustin Gongora
Independent Domination In Complementary Prisms., Joel Agustin Gongora
Electronic Theses and Dissertations
Let G be a graph and G̅ be the complement of G. The complementary prism GG̅ of G is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. For example, if G is a 5-cycle, then GG̅ is the Petersen graph. In this paper we investigate independent domination in complementary prisms.
Decompositions Of Mixed Graphs With Partial Orientations Of The P4., Adam M. Meadows
Decompositions Of Mixed Graphs With Partial Orientations Of The P4., Adam M. Meadows
Electronic Theses and Dissertations
A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. A mixed graph on V vertices is an ordered pair (V,C), where V is a set of vertices, |V| = v, and C is a set of ordered and unordered pairs, denoted (x, y) and [x, y] respectively, of elements of V [8]. An ordered pair (x …
Locating-Domination In Complementary Prisms., Kristin Renee Stone Holmes
Locating-Domination In Complementary Prisms., Kristin Renee Stone Holmes
Electronic Theses and Dissertations
Let G = (V (G), E(G)) be a graph and G̅ be the complement of G. The complementary prism of G, denoted GG̅, is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. A set D ⊆ V (G) is a locating-dominating set of G if for every u ∈ V (G)D, its neighborhood N(u)⋂D is nonempty and distinct from N( …
Cyclic, F-Cyclic, And Bicyclic Decompositions Of The Complete Graph Into The 4-Cycle With A Pendant Edge., Daniel Shelton Cantrell
Cyclic, F-Cyclic, And Bicyclic Decompositions Of The Complete Graph Into The 4-Cycle With A Pendant Edge., Daniel Shelton Cantrell
Electronic Theses and Dissertations
In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of:
(1) a single cycle of length v,
(2) f fixed points and a cycle of length v − f, or
(3) two disjoint cycles.
The purpose of this thesis is to give necessary and sufficient conditions for the existence of cyclic, f-cyclic, and bicyclic Q-decompositions of Kv.
Restrained And Other Domination Parameters In Complementary Prisms., Wyatt Jules Desormeaux
Restrained And Other Domination Parameters In Complementary Prisms., Wyatt Jules Desormeaux
Electronic Theses and Dissertations
In this thesis, we will study several domination parameters of a family of graphs known as complementary prisms. We will first present the basic terminology and definitions necessary to understand the topic. Then, we will examine the known results addressing the domination number and the total domination number of complementary prisms. After this, we will present our main results, namely, results on the restrained domination number of complementary prisms. Subsequently results on the distance - k domination number, 2-step domination number and stratification of complementary prisms will be presented. Then, we will characterize when a complementary prism is Eulerian or …
Double Domination Of Complementary Prisms., Lamont D. Vaughan
Double Domination Of Complementary Prisms., Lamont D. Vaughan
Electronic Theses and Dissertations
The complementary prism of a graph G is obtained from a copy of G and its complement G̅ by adding a perfect matching between the corresponding vertices of G and G̅. For any graph G, a set D ⊆ V (G) is a double dominating set (DDS) if that set dominates every vertex of G twice. The double domination number, denoted γ×2(G), is the cardinality of a minimum double dominating set of G. We have proven results on graphs of small order, specific families and lower bounds on γ×2 …
Finding Edge And Vertex Induced Cycles Within Circulants., Trina Marcella Wooten
Finding Edge And Vertex Induced Cycles Within Circulants., Trina Marcella Wooten
Electronic Theses and Dissertations
Let H be a graph. G is a subgraph of H if V (G) ⊆ V (H) and E(G) ⊆ E(H). The subgraphs of H can be used to determine whether H is planar, a line graph, and to give information about the chromatic number. In a recent work by Beeler and Jamison [3], it was shown that it is difficult to obtain an automorphic decomposition of a triangle-free graph. As many of their examples involve circulant graphs, it is of particular interest to find triangle-free subgraphs within circulants. As …
On The Attainability Of Upper Bounds For The Circular Chromatic Number Of K4-Minor-Free Graphs., Tracy Lance Holt
On The Attainability Of Upper Bounds For The Circular Chromatic Number Of K4-Minor-Free Graphs., Tracy Lance Holt
Electronic Theses and Dissertations
Let G be a graph. For k ≥ d ≥ 1, a k/d -coloring of G is a coloring c of vertices of G with colors 0, 1, 2, . . ., k - 1, such that d ≤ | c(x) - c(y) | ≤ k - d, whenever xy is an edge of G. We say that the circular chromatic number of G, denoted χc(G), is equal to the smallest k/d where a k/d -coloring exists. In [6], Pan and …
Packings And Coverings Of Various Complete Digraphs With The Orientations Of A 4-Cycle., Melody Elaine Cooper
Packings And Coverings Of Various Complete Digraphs With The Orientations Of A 4-Cycle., Melody Elaine Cooper
Electronic Theses and Dissertations
There are four orientations of cycles on four vertices. Necessary and sufficient conditions are given for covering complete directed digraphs Dv, packing and covering complete bipartite digraphs, Dm,n, and packing and covering the complete digraph on v vertices with hole of size w, D(v,w), with three of the orientations of a 4-cycle, including C4, X, and Y.
Chromatic Number Of The Alphabet Overlap Graph, G(2, K , K-2)., Jerry Brent Farley
Chromatic Number Of The Alphabet Overlap Graph, G(2, K , K-2)., Jerry Brent Farley
Electronic Theses and Dissertations
A graph G(a, k, t) is called an alphabet overlap graph where a, k, and t are positive integers such that 0 ≤ t < k and the vertex set V of G is defined as, V = {v : v = (v1v2...vk); vi ∊ {1, 2, ..., a}, (1 ≤ i ≤ k)}. That is, each vertex, v, is a word of length k over an alphabet of size a. There exists an edge between two vertices u, …
Decomposition, Packings And Coverings Of Complete Digraphs With A Transitive-Triple And A Pendant Arc., Janice Gail Lewenczuk
Decomposition, Packings And Coverings Of Complete Digraphs With A Transitive-Triple And A Pendant Arc., Janice Gail Lewenczuk
Electronic Theses and Dissertations
In the study of design theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K3∪{e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings and coverings of the complete digraph with each of the six transitive triples with a pendant arc.
Decompositions, Packings, And Coverings Of Complete Directed Gaphs With A 3-Circuit And A Pendent Arc., Chrys Gwellem
Decompositions, Packings, And Coverings Of Complete Directed Gaphs With A 3-Circuit And A Pendent Arc., Chrys Gwellem
Electronic Theses and Dissertations
In the study of Graph theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K3 ∪ {e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings, and coverings of the complete digraph with the two 3-circuit with a pendant arc orientations.
Tricyclic Steiner Triple Systems With 1-Rotational Subsystems., Quan Duc Tran
Tricyclic Steiner Triple Systems With 1-Rotational Subsystems., Quan Duc Tran
Electronic Theses and Dissertations
A Steiner triple system of order v, denoted STS(v), is said to be tricyclic if it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this thesis we give necessary and sufficient conditions for the existence of a tricyclic STS(v) when one of the cycles is of length one. In this case, the STS(v) will contain a subsystem which admits an automorphism consisting of a fixed point and a single cycle. The subsystem is said to be 1-rotational.
Alliance Partitions In Graphs., Jason Lachniet
Alliance Partitions In Graphs., Jason Lachniet
Electronic Theses and Dissertations
For a graph G=(V,E), a nonempty subset S contained in V is called a defensive alliance if for each v in S, there are at least as many vertices from the closed neighborhood of v in S as in V-S. If there are strictly more vertices from the closed neighborhood of v in S as in V-S, then S is a strong defensive alliance. A (strong) defensive alliance is called global if it is also a dominating set of G. The alliance partition number (respectively, strong …
Trees With Unique Minimum Locating-Dominating Sets., Stephen M. Lane
Trees With Unique Minimum Locating-Dominating Sets., Stephen M. Lane
Electronic Theses and Dissertations
A set S of vertices in a graph G = (V, E) is a locating-dominating set if S is a dominating set of G, and every pair of distinct vertices {u, v} in V - S is located with respect to S, that is, if the set of neighbors of u that are in S is not equal to the set of neighbors of v that are in S. We give a construction of trees that have unique minimum locating-dominating sets.
Double Domination Edge Critical Graphs., Derrick Wayne Thacker
Double Domination Edge Critical Graphs., Derrick Wayne Thacker
Electronic Theses and Dissertations
In a graph G=(V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ∈ E(G̅), the double domination number of G+uv is less than the double domination number of G. We investigate properties of double domination edge critical graphs. In particular, we characterize the double domination edge critical trees and …
On The Chromatic Number Of The Ao(2, K , K-1) Graphs., Navya Arora
On The Chromatic Number Of The Ao(2, K , K-1) Graphs., Navya Arora
Electronic Theses and Dissertations
The alphabet overlap graph is a modification of the well known de Bruijn graph. De Bruijn graphs have been highly studied and hence many properties of these graphs have been determined. However, very little is known about alphabet overlap graphs. In this work we determine the chromatic number for a special case of these graphs.
We define the alphabet overlap graph by G = AO(a, k, t, where a, k and t are positive integers such that 0 ≤ t ≤ k. The vertex set of G is the set of all k …