Discrete Mathematics and Combinatorics Commons^™

Runs Of Identical Outcomes In A Sequence Of Bernoulli Trials, Matthew Riggle

Masters Theses & Specialist Projects

The Bernoulli distribution is a basic, well-studied distribution in probability. In this thesis, we will consider repeated Bernoulli trials in order to study runs of identical outcomes. More formally, for t ∈ N, we let Xt ∼ Bernoulli(p), where p is the probability of success, q = 1 − p is the probability of failure, and all Xt are independent. Then Xt gives the outcome of the tth trial, which is 1 for success or 0 for failure. For n, m ∈ N, we define Tn to be the number of trials needed to first observe n …

Controllability And Observability Of The Discrete Fractional Linear State-Space Model, Duc M. Nguyen

Masters Theses & Specialist Projects

This thesis aims to investigate the controllability and observability of the discrete fractional linear time-invariant state-space model. First, we will establish key concepts and properties which are the tools necessary for our task. In the third chapter, we will discuss the discrete state-space model and set up the criteria for these two properties. Then, in the fourth chapter, we will attempt to apply these criteria to the discrete fractional model. The general flow of our objectives is as follows: we start with the first-order linear difference equation, move on to the discrete system, then the fractional difference equation, and finally …

Strong Degrees In Single Valued Neutrosophic Graphs, Florentin Smarandache, Said Broumi, Assia Bakali, Seema Mehra, Mohamed Talea, Manjeet Singh

Branch Mathematics and Statistics Faculty and Staff Publications

The concept of single valued neutrosophic graphs (SVNGs) generalizes the concept of fuzzy graphs and intuitionistic fuzzy graphs. The purpose of this research paper is to define different types of strong degrees in SVNGs and introduce novel concepts, such as the vertex truth-membership, vertex indeterminacy-membership and falsity-membership sequence in SVNG with proof and numerical illustrations.

Policy-Preferred Paths In As-Level Internet Topology Graphs, Mehmet Engin Tozal

Theory & Applications of Graphs

Using Autonomous System (AS) level Internet topology maps to determine accurate AS-level paths is essential for network diagnostics, performance optimization, security enforcement, business policy management and topology-aware application development. One significant drawback that we have observed in many studies is simplifying the AS-level topology map of the Internet to an undirected graph, and then using the hop distance as a means to find the shortest paths between the ASes. A less significant drawback is restricting the shortest paths to only valley-free paths. Both approaches usually inflate the number of paths between ASes; introduce erroneous paths that do not conform to …

Design And Analysis Of Graph-Based Codes Using Algebraic Lifts And Decoding Networks, Allison Beemer

Department of Mathematics: Dissertations, Theses, and Student Research

Error-correcting codes seek to address the problem of transmitting information efficiently and reliably across noisy channels. Among the most competitive codes developed in the last 70 years are low-density parity-check (LDPC) codes, a class of codes whose structure may be represented by sparse bipartite graphs. In addition to having the potential to be capacity-approaching, LDPC codes offer the significant practical advantage of low-complexity graph-based decoding algorithms. Graphical substructures called trapping sets, absorbing sets, and stopping sets characterize failure of these algorithms at high signal-to-noise ratios. This dissertation focuses on code design for and analysis of iterative graph-based message-passing decoders. The …

Weak Dynamic Coloring Of Planar Graphs, Caroline Accurso, Vitaliy Chernyshov, Leaha Hand, Sogol Jahanbekam, Paul Wenger

Faculty Publications

The k-weak-dynamic number of a graph G is the smallest number of colors we need to color the vertices of G in such a way that each vertex v of degree d(v) sees at least min{k, d(v)} colors on its neighborhood. We use reducible configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.

Summary Of The Special Issue “Neutrosophic Information Theory And Applications” At “Information” Journal, Florentin Smarandache, Jun Ye

Branch Mathematics and Statistics Faculty and Staff Publications

Over a period of seven months (August 2017–February 2018), the Special Issue dedicated to “Neutrosophic Information Theory and Applications” by the “Information” journal (ISSN 2078-2489), located in Basel, Switzerland, was a success. The Guest Editors, Prof. Dr. Florentin Smarandache from the University of New Mexico (USA) and Prof. Dr. Jun Ye from the Shaoxing University (China), were happy to select—helped by a team of neutrosophic reviewers from around the world, and by the “Information” journal editors themselves—and publish twelve important neutrosophic papers, authored by 27 authors and coauthors. There were a variety of neutrosophic topics studied and used by the …

Traveling In Networks With Blinking Nodes, Braxton Carrigan, James Hammer

Theory & Applications of Graphs

We say that a blinking node system modulo n is an ordered pair (G,L) where G is a graph and L is an on-labelling which indicates when vertices can be visited. An On-Hamiltonian walk is a sequence of all the vertices of G such that the position of each vertex modulo n is an integer of the label of that vertex. This paper will primarily investigate finding the shortest On-Hamiltonian walks in a blinking node system on complete graphs and complete bipartite graphs but also establishes the terminology and initial observations for working with blinking node systems on other graphs.

The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler

LSU Doctoral Dissertations

This thesis is motivated by a graph-theoretical result of Maffray, which states that a 2-connected graph with no odd cycles exceeding length 3 is bipartite, is isomorphic to K_4, or is a collection of triangles glued together along a common edge. We first prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is M(K_4) or F_7, or M is the cycle matroid of a graph consisting of a collection of triangles glued together along a common edge. This result implies that a 2-connected loopless graph G …

An Extension Of The Jeu De Taquin, Joanna Mckinney

Theses, Dissertations and Capstones

The Knuth transformations on words, the jeu de taquin moves on tableaux, and the Robinson–Schensted–Knuth algorithm produce the same equivalence classes for words. By observing the connections between these three methods we find and prove there exists connections between the Assaf–Knuth transformations, our extension of the jeu de taquin, and p-RSK. We know there exists an algebraic way to expand Macdonald polynomials in terms of the Schur functions. The form of the expansion implies there should be a combinatorial way to find the expansion. Loehr found a Robinson–Schensted–Knuth like algorithm that works in some cases. By finding an extension of …

An Incidence Approach To The Distinct Distances Problem, Bryce Mclaughlin

HMC Senior Theses

In 1946, Erdös posed the distinct distances problem, which asks for the minimum number of distinct distances that any set of n points in the real plane must realize. Erdös showed that any point set must realize at least &Omega(n^1/2) distances, but could only provide a construction which offered &Omega(n/&radic(log(n)))$ distances. He conjectured that the actual minimum number of distances was &Omega(n^1-&epsilon) for any &epsilon > 0, but that sublinear constructions were possible. This lower bound has been improved over the years, but Erdös' conjecture seemed to hold until in 2010 Larry Guth and Nets Hawk Katz …

Hilbert Bases, Descent Statistics, And Combinatorial Semigroup Algebras, Mccabe J. Olsen

Theses and Dissertations--Mathematics

The broad topic of this dissertation is the study of algebraic structure arising from polyhedral geometric objects. There are three distinct topics covered over three main chapters. However, each of these topics are further linked by a connection to the Eulerian polynomials.

Chapter 2 studies Euler-Mahonian identities arising from both the symmetric group and generalized permutation groups. Specifically, we study the algebraic structure of unit cube semigroup algebra using Gröbner basis methods to acquire these identities. Moreover, this serves as a bridge between previous methods involving polyhedral geometry and triangulations with descent bases methods arising in representation theory.

In Chapter …

A Combinatorial Miscellany: Antipodes, Parking Cars, And Descent Set Powers, Alexander Thomas Happ

Theses and Dissertations--Mathematics

In this dissertation we first introduce an extension of the notion of parking functions to cars of different sizes. We prove a product formula for the number of such sequences and provide a refinement using a multi-parameter extension of the Abel--Rothe polynomial. Next, we study the incidence Hopf algebra on the noncrossing partition lattice. We demonstrate a bijection between the terms in the canceled chain decomposition of its antipode and noncrossing hypertrees. Thirdly, we analyze the sum of the 𝑟th powers of the descent set statistic on permutations and how many small prime factors occur in these numbers. These results …

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.

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.