Discrete Mathematics and Combinatorics Commons^™

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.

Planar Graphs, Biplanar Graphs And Graph Thickness, Sean M. Hearon

Electronic Theses, Projects, and Dissertations

A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.

Bounds On The Expected Size Of The Maximum Agreement Subtree, Colby Long, Daniel Irving Bernstein, Lam Si Tung Ho, Mike Steel, Katherine St. John, Seth Sullivant

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Exploring The Space Of Rna Secondary Structures, Heather C. Smith

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Markov Chains On Graphical Models Of Gene Regulation, Megan Bernstein

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Genome Rearrangement: Graphs And Matrices, Jeffrey Davis

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

On The Expected Number Of Crossings In A Tanglegram, Eva Czabarka

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

On The Perfect Reconstruction Of The Structure Of Dynamic Networks, Alan Veliz-Cuba

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Spectral Graph Theory And New Stability Measures For Deterministic Gene Regulatory Networks, Fusun Akman, Devin Akman

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Cycle Structures Of Orthomorphisms Extending Partial Orthomorphisms Of Boolean Groups, Nichole Louise Schimanski, John S. Caughman Iv

Mathematics and Statistics Faculty Publications and Presentations

A partial orthomorphism of a group GG (with additive notation) is an injection π:S→G for some S⊆G such that π(x)−x ≠ π(y) for all distinct x,y∈S. We refer to |S| as the size of π, and if S=G, then π is an orthomorphism. Despite receiving a fair amount of attention in the research literature, many basic questions remain concerning the number of orthomorphisms of a given group, and what cycle types these permutations have.

It is known that conjugation by automorphisms of G forms a group action on the set of orthomorphisms of G. In this paper, we consider the …

On The Geodesic Centers Of Polygonal Domains, Haitao Wang

Computer Science Faculty and Staff Publications

In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain P of n vertices. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of P that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the size of the shortest path map equivalence decomposition of P, which is known to be O(n^{10}). One key observation is a pi-range property on shortest path lengths when points are moving. With these observations, …

Improving Proof-Writing With Reading Guides, Mike Janssen

Faculty Work Comprehensive List

One of the barriers in the transition to advanced mathematics is that the proofs and ideas in even the best mathematics texts must be read more carefully than many students are accustomed to. Yet in order to learn to write proofs well, one must learn how to read proofs well. Borrowing an idea from Lewis Ludwig, I flipped my introduction to proofs (discrete structures) course in Spring 2016 with the use of reading guides. Each day, students were responsible for reading a section of the text and completing a worksheet that highlighted the main points, asked students to create their …

An Update On A Few Permanent Conjectures, Fuzhen Zhang

Mathematics Faculty Articles

We review and update on a few conjectures concerning matrix permanent that are easily stated, understood, and accessible to general math audience. They are: Soules permanent-on-top conjecture†, Lieb permanent dominance conjecture, Bapat and Sunder conjecture† on Hadamard product and diagonal entries, Chollet conjecture on Hadamard product, Marcus conjecture on permanent of permanents, and several other conjectures. Some of these conjectures are recently settled; some are still open.We also raise a few new questions for future study. (†conjectures have been recently settled negatively.)

Combinatorics Of The Sonnet, Terry S. Griggs

Journal of Humanistic Mathematics

Using a definition of a sonnet, the number of basic rhyming schemes is enumerated. This is then used to discuss the 86 sonnets which appear in John Clare's The Rural Muse.

Impartial Avoidance And Achievement Games For Generating Symmetric And Alternating Groups, Bret J. Benesh, Dana C. Ernst, Nándor Sieben

Mathematics Faculty Publications

Anderson and Harary introduced two impartial games on finite groups. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly-selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. We determine the nim-numbers, and therefore the outcomes, of these games for symmetric and alternating groups.

Nullification Of Torus Knots And Links, Zachary S. Bettersworth

Masters Theses & Specialist Projects

Knot nullification is an unknotting operation performed on knots and links that can be used to model DNA recombination moves of circular DNA molecules in the laboratory. Thus nullification is a biologically relevant operation that should be studied.

Nullification moves can be naturally grouped into two classes: coherent nullification, which preserves the orientation of the knot, and incoherent nullification, which changes the orientation of the knot. We define the coherent (incoherent) nullification number of a knot or link as the minimal number of coherent (incoherent) nullification moves needed to unknot any knot or link. This thesis concentrates on the study …

Independent Domination In Some Wheel Related Graphs, S. K. Vaidya, R. M. Pandit

Applications and Applied Mathematics: An International Journal (AAM)

A set S of vertices in a graph G is called an independent dominating set if S is both independent and dominating. The independent domination number of G is the minimum cardinality of an independent dominating set in G . In this paper, we investigate the exact value of independent domination number for some wheel related graphs.

Cobb-Douglas Based Firm Production Model Under Fuzzy Environment And Its Solution Using Geometric Programming, Palash Mandal, Arindam Garai, Tapan K. Roy

Applications and Applied Mathematics: An International Journal (AAM)

In this paper, we consider Cobb-Douglas production function based model in a firm under fuzzy environment, and its solution technique by making use of geometric programming. A firm may use many finite inputs such as labour, capital, coal, iron etc. to produce one single output. It is well known that the primary intention of using production function is to determine maximum output for any given combination of inputs. Also, the firm may gain competitive advantages if it can buy and sell in any quantities at exogenously given prices, independent of initial production decisions. On the other hand, in reality, constraints …

On Local Asymptotic Stability Of Q-Fractional Nonlinear Dynamical Systems, Ilknur Koca, Elif Demirci

Applications and Applied Mathematics: An International Journal (AAM)

In this paper, locally asymptotic stability of q-fractional order nonlinear dynamical systems is introduced and studied. The sufficient conditions for local stability of such dynamical systems are obtained. Also, useful definitions of fractional order q-integrals and q-derivatives are recalled. Finally, a q-fractional order nonlinear dynamical model is considered.

Domination Integrity Of Line Splitting Graph And Central Graph Of Path, Cycle And Star Graphs, Sultan S. Mahde, Veena Mathad

Applications and Applied Mathematics: An International Journal (AAM)

The domination integrity of a connected graph G = (V (G);E(G)) is denoted as DI(G) and defined by DI(G) = min{|S| + m(G - S)}, where S is a dominating set and m(G-S) is the order of a maximum component of G-S. This paper discusses domination integrity of line splitting graph and central graph of some graphs.

3-Total Super Sum Cordial Labeling By Applying Operations On Some Graphs, Abha Tenguria, Rinku Verma

Applications and Applied Mathematics: An International Journal (AAM)

The sum cordial labeling is a variant of cordial labeling. In this paper, we investigate 3-Total Super Sum Cordial labeling. This labeling is discussed by applying union operation on some of the graphs. A vertex labeling is assigned as a whole number within the range. For each edge of the graph, assign the label, according to some definite rule, defined for the investigated labeling. Any graph which satisfies 3-Total Super Sum Cordial labeling is known as the 3-Total Super Sum Cordial graphs. Here, we prove that some of the graphs like the union of Cycle and Path graphs, the union …

Upset Paths And 2-Majority Tournaments, Rana Ali Alshaikh

Electronic Theses, Projects, and Dissertations

In 2005, Alon, et al. proved that tournaments arising from majority voting scenarios have minimum dominating sets that are bounded by a constant that depends only on the notion of what is meant by a majority. Moreover, they proved that when a majority means that Candidate A beats Candidate B when Candidate A is ranked above Candidate B by at least two out of three voters, the tournament used to model this voting scenario has a minimum dominating set of size at most three. This result gives 2-majority tournaments some significance among all tournaments and motivates us to investigate when …

Chromatic Connectivity Of Graphs, Elliot Laforge

Dissertations

No abstract provided.

Ádám's Conjecture And Arc Reversal Problems, Claudio D. Salas

Electronic Theses, Projects, and Dissertations

A. Ádám conjectured that for any non-acyclic digraph D, there exists an arc whose reversal reduces the total number of cycles in D. In this thesis we characterize and identify structure common to all digraphs for which Ádám's conjecture holds. We investigate quasi-acyclic digraphs and verify that Ádám's conjecture holds for such digraphs. We develop the notions of arc-cycle transversals and reversal sets to classify and quantify this structure. It is known that Ádám's conjecture does not hold for certain infinite families of digraphs. We provide constructions for such counterexamples to Ádám's conjecture. Finally, we address a conjecture …

Hill's Diagrammatic Method And Reduced Graph Powers, Gregory D. Smith, Richard Hammack

Biology and Medicine Through Mathematics Conference

No abstract provided.

A Computational Investigation Of Large Gaps In Contingency Tables, Noah J. Watson

Senior Honors Projects, 2010-2019

Integer programming can be used to find upper and lower bounds on the cells of a multi-dimensional contingency table using the information from the released margins. The linear relaxation of these programs also provides bounds and the discrepancy between these bounds, the integer programming gap, can be large. While the more notable examples of large gaps have been shown to be rare, here we provide some results on the rarity of large gaps on small tables.

Math And Sudoku: Exploring Sudoku Boards Through Graph Theory, Group Theory, And Combinatorics, Kyle Oddson

Student Research Symposium

Encoding Sudoku puzzles as partially colored graphs, we state and prove Akman’s theorem [1] regarding the associated partial chromatic polynomial [5]; we count the 4x4 sudoku boards, in total and fundamentally distinct; we count the diagonally distinct 4x4 sudoku boards; and we classify and enumerate the different structure types of 4x4 boards.