Discrete Mathematics and Combinatorics Commons^™

Influences Of Probability Instruction On Undergraduates' Understanding Of Counting Processes, Kayla Blyman

Theses and Dissertations--Education Sciences

Historically, students in an introductory finite mathematics course at a major university in the mid-south have struggled the most with the counting and probability unit, leading instructors to question if there was a better way to help students master the material. The purpose of this study was to begin to understand connections that undergraduate finite mathematics students are making between counting and probability. By examining student performance in counting and probability, this study provides insights that inform future instruction in courses that include counting and probability. Consequently, this study lays the groundwork for future inquiries in the field of undergraduate …

Note On 6-Regular Graphs On The Klein Bottle, Michiko Kasai, Naoki Matsumoto, Atsuhiro Nakamoto, Takayuki Nozawa, Hiroki Seno, Yosuke Takiguchi

Theory & Applications of Graphs

Altshuler classified six regular graphs on the torus, but Thomassen and Negami gave different classifications for six regular graphs on the Klein bottle. In this note, we unify those two classifications, pointing out their difference and similarity.

Edge-Transitive Bipartite Direct Products, Cameron M. Crenshaw

Theses and Dissertations

In their recent paper ``Edge-transitive products," Hammack, Imrich, and Klavzar showed that the direct product of connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive, and at least one is arc-transitive. However, little is known when the product is bipartite. This thesis extends this result (in part) for the case of bipartite graphs using a new technique called "stacking." For R-thin, connected, bipartite graphs A and B, we show that A x B is arc-transitive if and only if A and B are both arc-transitive. Further, we show A x B is edge-transitive only …

Generalized Interval Valued Neutrosophic Graphs Of First Type, Florentin Smarandache, Said Broumi, Mohamed Talea, Assia Bakali, Ali Hassan

Branch Mathematics and Statistics Faculty and Staff Publications

In this paper, motivated by the notion of generalized single valued neutrosophic graphs of first type, we defined a new neutrosophic graphs named generalized interval valued neutrosophic graphs of first type (GIVNG1) and presented a matrix representation for it and studied few properties of this new concept. The concept of GIVNG1 is an extension of generalized fuzzy graphs (GFG1) and generalized single valued neutrosophic of first type (GSVNG1).

The Partition Lattice In Many Guises, Dustin G. Hedmark

Theses and Dissertations--Mathematics

This dissertation is divided into four chapters. In Chapter 2 the equivariant homology groups of upper order ideals in the partition lattice are computed. The homology groups of these filters are written in terms of border strip Specht modules as well as in terms of links in an associated complex in the lattice of compositions. The classification is used to reproduce topological calculations of many well-studied subcomplexes of the partition lattice, including the d-divisible partition lattice and the Frobenius complex. In Chapter 3 the box polynomial B_{m,n}(x) is defined in terms of all integer partitions that fit in an m …

Colorings Of Hamming-Distance Graphs, Isaiah H. Harney

Theses and Dissertations--Mathematics

Hamming-distance graphs arise naturally in the study of error-correcting codes and have been utilized by several authors to provide new proofs for (and in some cases improve) known bounds on the size of block codes. We study various standard graph properties of the Hamming-distance graphs with special emphasis placed on the chromatic number. A notion of robustness is defined for colorings of these graphs based on the tolerance of swapping colors along an edge without destroying the properness of the coloring, and a complete characterization of the maximally robust colorings is given for certain parameters. Additionally, explorations are made into …

Some Take-Away Games On Discrete Structures, Kristen M. Barnard

Theses and Dissertations--Mathematics

The game of Subset Take-Away is an impartial combinatorial game posed by David Gale in 1974. The game can be played on various discrete structures, including but not limited to graphs, hypergraphs, polygonal complexes, and partially ordered sets. While a universal winning strategy has yet to be found, results have been found in certain cases. In 2003 R. Riehemann focused on Subset Take-Away on bipartite graphs and produced a complete game analysis by studying nim-values. In this work, we extend the notion of Take-Away on a bipartite graph to Take-Away on particular hypergraphs, namely oddly-uniform hypergraphs and evenly-uniform hypergraphs whose …

An Updated Survey On Rainbow Connections Of Graphs - A Dynamic Survey, Xueliang Li, Yuefang Sun

Theory & Applications of Graphs

The concept of rainbow connection was introduced by Chartrand, Johns, McKeon and Zhang in 2008. Nowadays it has become a new and active subject in graph theory. There is a book on this topic by Li and Sun in 2012, and a survey paper by Li, Shi and Sun in 2013. More and more researchers are working in this field, and many new papers have been published in journals. In this survey we attempt to bring together most of the new results and papers that deal with this topic. We begin with an introduction, and then try to organize the …

Edge Colorings Of K(M,N) With M+N-1 Colors Which Forbid Rainbow Cycles, Peter Johnson, Claire Zhang

Theory & Applications of Graphs

For positive integers m, n, the greatest number of colors that can appear in an edge coloring of K(m,n) which avoids rainbow cycles is m + n - 1. Here these colorings are constructively characterized. It turns out that these colorings can be encoded by certain vertex labelings of full binary trees with m + n leafs.

An Eternal Domination Problem In Grids, William Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello

Theory & Applications of Graphs

A dynamic domination problem in graphs is considered in which an infinite sequence of attacks occur at vertices with mobile guards; the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack, the vertices containing guards must form a dominating set of the graph. The minimum number of guards that can defend the graph against such an arbitrary sequence of attacks is called the m-eviction number of the graph. In this paper, the m-eviction …

Two Short Proofs Of The Perfect Forest Theorem, Yair Caro, Josef Lauri, Christina Zarb

Theory & Applications of Graphs

A perfect forest is a spanning forest of a connected graph G, all of whose components are induced subgraphs of G and such that all vertices have odd degree in the forest. A perfect forest can be thought of as a generalization of a perfect matching since, in a matching, all components are trees on one edge. Scott first proved the Perfect Forest Theorem, namely, that every connected graph of even order has a perfect forest. Gutin then gave another proof using linear algebra.

We give here two very short proofs of the Perfect Forest Theorem which use only …

Application Of An Extremal Result Of Erdős And Gallai To The (N,K,T) Problem, Matt Noble, Peter Johnson, Dean Hoffman, Jessica Mcdonald

Theory & Applications of Graphs

An extremal result about vertex covers, attributed by Hajnal to Erdős and Gallai, is applied to prove the following: If n, k, and t are integers satisfying n ≥ k ≥ t ≥ 3 and k ≤ 2t - 2, and G is a graph with the minimum number of edges among graphs on n vertices with the property that every induced subgraph on k vertices contains a complete subgraph on t vertices, then every component of G is complete.

Graph Invariants Of Trees With Given Degree Sequence, Rachel Bass

College of Graduate Studies: Theses & Dissertations

Graph invariants are functions defined on the graph structures that stay the same under taking graph isomorphisms. Many such graph invariants, including some commonly used graph indices in Chemical Graph Theory, are defined on vertex degrees and distances between vertices. We explore generalizations of such graph indices and the corresponding extremal problems in trees. We will also briefly mention the applications of our results.

Combinatorics Of Compositions, Meghann M. Gibson

College of Graduate Studies: Theses & Dissertations

Integer compositions and related enumeration problems have been extensively studied. The cyclic analogues of such questions, however, have significantly fewer results. In this thesis, we follow the cyclic construction of Flajolet and Soria to obtain generating functions for cyclic compositions and n-color cyclic compositions with various restrictions. With these generating functions we present some statistics and asymptotic formulas for the number of compositions and parts in such compositions. Combinatorial explanations are also provided for many of the enumerative observations presented.

Network Analytics For The Mirna Regulome And Mirna-Disease Interactions, Joseph Jayakar Nalluri

Theses and Dissertations

miRNAs are non-coding RNAs of approx. 22 nucleotides in length that inhibit gene expression at the post-transcriptional level. By virtue of this gene regulation mechanism, miRNAs play a critical role in several biological processes and patho-physiological conditions, including cancers. miRNA behavior is a result of a multi-level complex interaction network involving miRNA-mRNA, TF-miRNA-gene, and miRNA-chemical interactions; hence the precise patterns through which a miRNA regulates a certain disease(s) are still elusive. Herein, I have developed an integrative genomics methods/pipeline to (i) build a miRNA regulomics and data analytics repository, (ii) create/model these interactions into networks and use optimization techniques, motif …

Dynamics Of Gene Networks In Cancer Research, Paul Scott

College of Graduate Studies: Theses & Dissertations

Cancer prevention treatments are being researched to see if an optimized treatment schedule would decrease the likelihood of a person being diagnosed with cancer. To do this we are looking at genes involved in the cell cycle and how they interact with one another. Through each gene expression during the life of a normal cell we get an understanding of the gene interactions and test these against those of a cancerous cell. First we construct a simplified network model of the normal gene network. Once we have this model we translate it into a transition matrix and force changes on …

Pattern Containment In Circular Permutations, Charles Lanning

College of Graduate Studies: Theses & Dissertations

Pattern containment in permutations, as opposed to pattern avoidance, involves two aspects. The first is to contain every pattern at least once from a given set, known as finding superpatterns; while the second is to contain some given pattern as many times as possible, known as pattern packing. In this thesis, we explore these two questions in circular permutations and present some interesting observations. We also raise some questions and propose some directions for future study.

Characterizations Of Families Of Rectangular, Finite Impulse Response, Para-Unitary Systems, Daniel Alpay, Palle Jorgensen, Izchak Lewkowicz

Mathematics, Physics, and Computer Science Faculty Articles and Research

We here study Finite Impulse Response (FIR) rectangular, not necessarily causal, systems which are (para)-unitary on the unit circle (=the class U). First, we offer three characterizations of these systems. Then, introduce a description of all FIRs in U, as copies of a real polytope, parametrized by the dimensions and the McMillan degree of the FIRs.

Finally, we present six simple ways (along with their combinations) to construct, from any FIR, a large family of FIRs, of various dimensions and McMillan degrees, so that whenever the original system is in U, so is the whole family.

A key role is …

The Use Of The Pivot Pairwise Relative Criteria Importance Assessment Method For Determining The Weights Of Criteria, Florentin Smarandache, Dragisa Stanujkic, Edmundas Kazimieras Zavadskas, Darjan Karabasevic, Zenonas Turskis

Branch Mathematics and Statistics Faculty and Staff Publications

The weights of evaluation criteria could have a significant impact on the results obtained by applying multiple criteria decision-making methods. Therefore, the two extensions of the SWARA method that can be used in cases when it is not easy, or even is impossible to reach a consensus on the expected importance of the evaluation criteria are proposed in this paper. The primary objective of the proposed extensions is to provide an understandable and easy-to-use approach to the collecting of respondents’ real attitudes towards the significance of evaluation criteria and to also provide an approach to the checking of the reliability …

Neutrosophic Operational Research - Vol. 2, Florentin Smarandache, Mohamed Abdel Basset, Victor Chang

Branch Mathematics and Statistics Faculty and Staff Publications

Foreword John R. Edwards This book is an excellent exposition of the use of Data Envelopment Analysis (DEA) to generate data analytic insights to make evidence-based decisions, to improve productivity, and to manage cost-risk and benefitopportunity in public and private sectors. The design and the content of the book make it an up-to-date and timely reference for professionals, academics, students, and employees, in particular those involved in strategic and operational decisionmaking processes to evaluate and prioritize alternatives to boost productivity growth, to optimize the efficiency of resource utilization, and to maximize the effectiveness of outputs and impacts to stakeholders. It …

Complex Valued Graphs For Soft Computing, Florentin Smarandache, W.B. Vasantha Kandasamy, Ilanthenral K

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time introduce in a systematic way the notion of complex valued graphs, strong complex valued graphs and complex neutrosophic valued graphs. Several interesting properties are defined, described and developed. Most of the conjectures which are open in case of usual graphs continue to be open problems in case of both complex valued graphs and strong complex valued graphs. We also give some applications of them in soft computing and social networks. At this juncture it is pertinent to keep on record that Dr. Tohru Nitta was the pioneer to use complex valued graphs …

Distribution Of Permutation Statistics Across Pattern Avoidance Classes, And The Search For A Denert-Associated Condition Equivalent To Pattern Avoidance, Joshua Thomas Agustin Davies

Dissertations, Master's Theses and Master's Reports

We begin with a discussion of the symmetricity of $\maj$ over $\des$ in pattern avoidance classes, and its relationship to $\maj$-Wilf equivalence. From this, we explore the distribution of permutation statistics across pattern avoidance for patterns of length 3 and 4.

We then begin discussion of Han's bijection, a bijection on permutations which sends the major index to Denert's statistic and the descent number to the (strong) excedance number. We show the existence of several infinite families of fixed points for Han's bijection.

Finally, we discuss the image of pattern avoidance classes under Han's bijection, for the purpose of finding …

Distance Magic-Type And Distance Antimagic-Type Labelings Of Graphs, Bryan Freyberg

Dissertations, Master's Theses and Master's Reports

Generally speaking, a distance magic-type labeling of a graph G of order n is a bijection f from the vertex set of the graph to the first n natural numbers or to the elements of a group of order n, with the property that the weight of each vertex is the same. The weight of a vertex x is defined as the sum (or appropriate group operation) of all the labels of vertices adjacent to x. If instead we require that all weights differ, then we refer to the labeling as a distance antimagic-type labeling. This idea can be generalized …

On A Class Of Quaternionic Positive Definite Functions And Their Derivatives, Daniel Alpay, Fabrizio Colombo, Irene Sabadini

Mathematics, Physics, and Computer Science Faculty Articles and Research

In this paper, we start the study of stochastic processes over the skew field of quaternions. We discuss the relation between positive definite functions and the covariance of centered Gaussian processes and the construction of stochastic processes and their derivatives. The use of perfect spaces and strong algebras and the notion of Fock space are crucial in this framework.

Adaptive Orthonormal Systems For Matrix-Valued Functions, Daniel Alpay, Fabrizio Colombo, Tao Qian, Irene Sabadini, Tao Qian

Mathematics, Physics, and Computer Science Faculty Articles and Research

In this paper we consider functions in the Hardy space Hp×q2 defined in the unit disc of matrix-valued. We show that it is possible, as in the scalar case, to decompose those functions as linear combinations of suitably modified matrix-valued Blaschke product, in an adaptive way. The procedure is based on a generalization to the matrix-valued case of the maximum selection principle which involves not only selections of suitable points in the unit disc but also suitable orthogonal projections. We show that the maximum selection principle gives rise to a convergent algorithm. Finally, we discuss the case of real-valued signals.

Functions Of The Infinitesimal Generator Of A Strongly Continuous Quaternionic Group, Daniel Alpay, Fabrizio Colombo, Jonathan Gantner, David P. Kimsey

Mathematics, Physics, and Computer Science Faculty Articles and Research

The analogue of the Riesz-Dunford functional calculus has been introduced and studied recently as well as the theory of semigroups and groups of linear quaternionic operators. In this paper we suppose that T is the infinitesimal generator of a strongly continuous group of operators (ZT (t))t2R and we show how we can define bounded operators f(T ), where f belongs to a class of functions which is larger than the class of slice regular functions, using the quaternionic Laplace-Stieltjes transform. This class will include functions that are slice regular on the S-spectrum of T but not necessarily at infinity. Moreover, …

A Generalized Polynomial Identity Arising From Quantum Mechanics, Shashikant B. Mulay, John J. Quinn, Mark A. Shattuck

Applications and Applied Mathematics: An International Journal (AAM)

We establish a general identity that expresses a Pfaffian of a certain matrix as a quotient of homogeneous polynomials. This identity arises in the study of weakly interacting many-body systems and its proof provides another way of realizing the equivalence of two proposed types of trial wave functions used to describe such systems. In the proof of our identity, we make use of only elementary linear algebra and combinatorics and thereby avoid use of more advanced conformal field theory in establishing the aforementioned equivalence.

The History Of Algorithmic Complexity, Audrey A. Nasar

Publications and Research

This paper provides a historical account of the development of algorithmic complexity in a form that is suitable to instructors of mathematics at the high school or undergraduate level. The study of algorithmic complexity, despite being deeply rooted in mathematics, is usually restricted to the computer science curriculum. By providing a historical account of algorithmic complexity through a mathematical lens, this paper aims to equip mathematics educators with the necessary background and framework for incorporating the analysis of algorithmic complexity into mathematics courses as early on as algebra or pre-calculus.

Latin Squares And Their Applications To Cryptography, Nathan O. Schmidt

Boise State University Theses and Dissertations

A latin square of order-n is an n x n array over a set of n symbols such that every symbol appears exactly once in each row and exactly once in each column. Latin squares encode features of algebraic structures. When an algebraic structure passes certain "latin square tests", it is a candidate for use in the construction of cryptographic systems. A transversal of a latin square is a list of n distinct symbols, one from each row and each column. The question regarding the existence of transversals in latin squares that encode the Cayley tables of finite groups …

Matching Transversal Edge Domination In Graphs, Anwar Alwardi

Applications and Applied Mathematics: An International Journal (AAM)

Let G =(V,E) be a graph. A subset X of E is called an edge dominating set of G if every edge in E - X is adjacent to some edge in X . An edge dominating set which intersects every maximum matching inG is called matching transversal edge dominating set. The minimum cardinality of a matching transversal edge dominating set is called the matching transversal edge domination number of G and is denoted by γ_mt(G). In this paper, we begin an investigation of this parameter.