Discrete Mathematics and Combinatorics Commons^™

3-Maps And Their Generalizations, Kevin J. Mccall

Theses and Dissertations

A 3-map is a 3-region colorable map. They have been studied by Craft and White in their paper 3-maps. This thesis introduces topological graph theory and then investigates 3-maps in detail, including examples, special types of 3-maps, the use of 3-maps to find the genus of special graphs, and a generalization known as n-maps.

Self-Assembly Of Dna Graphs And Postman Tours, Katie Bakewell

UNF Graduate Theses and Dissertations

DNA graph structures can self-assemble from branched junction molecules to yield solutions to computational problems. Self-assembly of graphs have previously been shown to give polynomial time solutions to hard computational problems such as 3-SAT and k-colorability problems. Jonoska et al. have proposed studying self-assembly of graphs topologically, considering the boundary components of their thickened graphs, which allows for reading the solutions to computational problems through reporter strands. We discuss weighting algorithms and consider applications of self-assembly of graphs and the boundary components of their thickened graphs to problems involving minimal weight Eulerian walks such as the Chinese Postman Problem and …

Notions Of Rough Neutrosophic Digraphs, Florentin Smarandache, Nabeela Ishfaq, Sidra Sayed, Muhammad Akram

Branch Mathematics and Statistics Faculty and Staff Publications

Graph theory has numerous applications in various disciplines, including computer networks, neural networks, expert systems, cluster analysis, and image capturing. Rough neutrosophic set (NS) theory is a hybrid tool for handling uncertain information that exists in real life. In this research paper, we apply the concept of rough NS theory to graphs and present a new kind of graph structure, rough neutrosophic digraphs. We present certain operations, including lexicographic products, strong products, rejection and tensor products on rough neutrosophic digraphs. We investigate some of their properties. We also present an application of a rough neutrosophic digraph in decision-making.

Subset Vertex Graphs For Social Networks, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time introduce the notion of subset vertex graph using the vertex set as the subset of the power set P(S), S is assumed in this book to be finite; however it can be finite or infinite. We have defined two types of subset vertex graphs, one is directed and the other one is not directed. The most important fact which must be kept in record is that for a given set of vertices there exists one and only one subset vertex graph be it of type I or type II. Several important and …

Mod Rectangular Natural Neutrosophic Numbers, Florentin Smarandache, K. Ilanthenral, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors introduce the new notion of MOD rectangular planes. The functions on them behave very differently when compared to MOD planes (square). These are different from the usual MOD planes. Algebraic structures on these MOD rectangular planes are defined and developed. However we have built only MOD interval natural neutrosophic products

Spanning Tree Problem With Neutrosophic Edge Weights, Florentin Smarandache, Said Broumi, Assia Bakali, Mohamed Talea, Arindam Dey, Le Hoang Son

Branch Mathematics and Statistics Faculty and Staff Publications

Neutrosophic set and neutrosophic logic theory are renowned theories to deal with complex, not clearly explained and uncertain real life problems, in which classical fuzzy sets/models may fail to model properly. This paper introduces an algorithm for finding minimum spanning tree (MST) of an undirected neutrosophic weighted connected graph (abbr. UNWCG) where the arc/edge lengths are represented by a single valued neutrosophic numbers. To build the MST of UNWCG, a new algorithm based on matrix approach has been introduced. The proposed algorithm is compared to other existing methods and finally a numerical example is provided.

On Saturation Numbers Of Ramsey-Minimal Graphs, Hunter M. Davenport

Honors Undergraduate Theses

Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H₁,...,H_k) if every k-edge-coloring of G contains a monochromatic copy of H_i in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring of G, we say c is a bad coloring if G contains no red K₃or blue K …

Polytopes Associated To Graph Laplacians, Marie Meyer

Theses and Dissertations--Mathematics

Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, P_G, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, P_D.

Basic properties of both families of simplices, P_G and P …

On The Density Of The Odd Values Of The Partition Function, Samuel Judge

Dissertations, Master's Theses and Master's Reports

The purpose of this dissertation is to introduce a new approach to the study of one of the most basic and seemingly intractable problems in partition theory, namely the conjecture that the partition function $p(n)$ is equidistributed modulo $2$. We provide a doubly-indexed, infinite family of conjectural identities in the ring of series $\Z_2[[q]]$, which relate $p(n)$ with suitable $t$-multipartition functions, and show how to, in principle, prove each such identity. We will exhibit explicit proofs for $32$ of our identities. However, the conjecture remains open in full generality. A striking consequence of these conjectural identities is that, under suitable …

Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell

Honors Theses

Bi-infinite words are sequences of characters that are infinite forwards and backwards; for example "...ababababab...". The Morse-Hedlund theorem says that a bi-infinite word f repeats itself, in at most n letters, if and only if the number of distinct subwords of length n is at most n. Using the example, "...ababababab...", there are 2 subwords of length 3, namely "aba" and "bab". Since 2 is less than 3, we must have that "...ababababab..." repeats itself after at most 3 letters. In fact it does repeat itself every two letters. …

Sparse Trees With A Given Degree Sequence, Ao Shen

College of Graduate Studies: Theses & Dissertations

In this thesis, we consider the properties of sparse trees and summarized a certain class of trees under some constraint (including with a given degree sequence, with given number of leaves, with given maximum degree, etc.) which have maximum Wiener index and the minimum number of subtrees at the same time. Wiener index is one of the most important topological indices in chemical graph theory. Steiner k�� Wiener index can be regarded as the generalization of Wiener index, when k = 2, Steiner Wiener index is the same as Wiener index. Steiner k�� Wiener index of a tree T is …

String C-Groups Of Order 1024, Yasushi Gomi, Mark L. Loyola, Ma. Louise Antonette N. De Las Peñas

Mathematics Faculty Publications

This paper determines the nondegenerate string C-groups of order 1024. For groups of rank 3, we use the technique of central extension of string C-groups of order 512. For groups of rank at least 4, we compute for quotients of universal string C-groups.

Generalized Matching Preclusion In Bipartite Graphs, Zachary Wheeler, Eddie Cheng, Dana Ferranti, Laszlo Liptak, Karthik Nataraj

Theory & Applications of Graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal such sets are precisely sets of edges incident to a single vertex. The conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond these, and it is defined as the minimum number of edges whose deletion results in a graph with neither isolated vertices nor perfect matchings. In this paper we generalize this concept to get a hierarchy of …

A General Lower Bound On Gallai-Ramsey Numbers For Non-Bipartite Graphs, Colton Magnant

Theory & Applications of Graphs

Given a graph H and a positive integer k, the k-color Gallai-Ramsey number gr_k(K3 : H) is defined to be the minimum number of vertices n for which any k-coloring of the complete graph K_n contains either a rainbow triangle or a monochromatic copy of H. The behavior of these numbers is rather well understood when H is bipartite but when H is not bipartite, this behavior is a bit more complicated. In this short note, we improve upon existing lower bounds for non-bipartite graphs H to a value that we conjecture to …

On The Planarity Of Generalized Line Graphs, Khawlah H. Alhulwah, Mohra Zayed, Ping Zhang

Theory & Applications of Graphs

One of the most familiar derived graphs is the line graph. The line graph L(G) of a graph G is that graph whose vertices are the edges of G where two vertices of L(G) are adjacent if the corresponding edges are adjacent in G. Two nontrivial paths P and Q in a graph G are said to be adjacent paths in G if P and Q have exactly one vertex in common and this vertex is an end-vertex of both P and Q. For an integer ℓ ≥ 2, the ℓ -line graph Lℓ (G) of a …

A Survey On Monochromatic Connections Of Graphs, Xueliang Li, Di Wu

Theory & Applications of Graphs

The concept of monochromatic connection of graphs was introduced by Caro and Yuster in 2011. Recently, a lot of results have been published about it.
In this survey, we attempt to bring together all the results that dealt with it.
We begin with an introduction, and then classify the results into the following categories: monochromatic connection coloring of edge-version, monochromatic connection coloring of vertex-version, monochromatic index, monochromatic connection coloring of total-version.

Pbw Bases And Marginally Large Tableaux In Type D, Ben Salisbury, Adam Schultze, Peter Tingley

Mathematics and Statistics: Faculty Publications and Other Works

We give an explicit description of the unique crystal isomorphism between two realizations of B(∞) in type D: that using marginally large tableaux and that using PBW monomials with respect to one particularly nice reduced expression of the longest word

Distributive Lattice Models Of The Type C One-Rowed Weyl Group Symmetric Functions, William Atkins

Murray State Theses and Dissertations

We present two families of diamond-colored distributive lattices – one known and one new – that we can show are models of the type C one-rowed Weyl symmetric functions. These lattices are constructed using certain sequences of positive integers that are visualized as filling the boxes of one-rowed partition diagrams. We show how natural orderings of these one-rowed tableaux produce our distributive lattices as sublattices of a more general object, and how a natural coloring of the edges of the associated order diagrams yields a certain diamond-coloring property. We show that each edge-colored lattice possesses a certain structure that is …

On The Domination Chain Of M By N Chess Graphs, Kathleen Johnson

Murray State Theses and Dissertations

A survey of the six domination chain parameters for both square and rectangular chess boards are discussed.