Discrete Mathematics and Combinatorics Commons^™

Domination Integrity Of Some Path Related Graphs, S. K. Vaidya, N. H. Shah

Applications and Applied Mathematics: An International Journal (AAM)

The stability of a communication network is one of the important parameters for network designers and users. A communication network can be considered to be highly vulnerable if the destruction of a few elements cause large damage and only few members are able to communicate. In a communication network several vulnerability measures like binding number, toughness, scattering number, integrity, tenacity, edge tenacity and rupture degree are used to determine the resistance of network to the disruption after the failure of certain nodes (vertices) or communication links (edges). Domination theory also provides a model to measure the vulnerability of a graph …

Private Out-Domination Number Of Generalized De Bruijn Digraphs, G. Marimuthu, B. Johnson

Applications and Applied Mathematics: An International Journal (AAM)

Dominating sets are widely applied in the design and efficient use of computer networks. They can be used to decide the placement of limited resources, so that every node has access to the resource through neighbouring node. The most efficient solution is one that avoids duplication of access to the resources. This more restricted version of minimum dominating set is called an private dominating set. A vertex v in a digraph D is called a private out-neighbor of the vertex u in S (subset of V(D)) if u is the only element in the intersection of in-neighborhood set of v …

Difference Cordial Labeling Of Graphs Obtained From Triangular Snakes, R. Ponraj, S. S. Narayanan

Applications and Applied Mathematics: An International Journal (AAM)

In this paper, we investigate the difference cordial labeling behavior of corona of triangular snake with the graphs of order one and order two and also corona of alternative triangular snake with the graphs of order one and order two.

A Study Of Graphical Permutations, Jessica Thune

UNLV Theses, Dissertations, Professional Papers, and Capstones

A permutation π on a set of positive integers {a_1,a_2,...,a_n} is said to be graphical if there exists a graph containing exactly a_i vertices of degree (a_i) for each i. It has been shown that for positive integers with a_1

Crystal Graphs, Tokuyama's Theorem, And The Gindikin-Karpelevic Formula For G2, Holley Friedlander, Louis Gaudet, Paul E. Gunnells

Paul Gunnells

We conjecture a deformation of the Weyl character formula for type G2 in the spirit of Tokuyama’s formula for type A . Using our conjecture, we prove a combinatorial version of the Gindikin–Karpelevič formula for G2 , in the spirit of Bump–Nakasuji’s formula for type A .

A Potential Foundation For Emergent Space-Time, Kevin H. Knuth, Newshaw Bahreyni

Physics Faculty Scholarship

We present a novel derivation of both the Minkowski metric and Lorentz transformations from the consistent quantification of a causally ordered set of events with respect to an embedded observer. Unlike past derivations, which have relied on assumptions such as the existence of a 4-dimensional manifold, symmetries of space-time, or the constant speed of light, we demonstrate that these now familiar mathematics can be derived as the unique means to consistently quantify a network of events. This suggests that space-time need not be physical, but instead the mathematics of space and time emerges as the unique way in which an …

The Lp Relaxation Orthogonal Array Polytope And Its Permutation Symmetries, Andrew J. Geyer, Dursun A. Bulutoglu, Steven J. Rosenberg

Faculty Publications

Symmetry plays a fundamental role in design of experiments. In particular, symmetries of factorial designs that preserve their statistical properties are exploited to find designs with the best statistical properties. By using a result proved by Rosenberg [6], the concept of the LP relaxation orthogonal array polytope is developed and studied. A complete characterization of the permutation symmetry group of this polytope is made. Also, this characterization is verified computationally for many cases. Finally, a proof is provided.

Physics: Rethinking The Foundations, Kevin H. Knuth

Physics Faculty Scholarship

Physics is traditionally conceived of as a set of laws that universally governs the behavior of physical systems. These laws, however they are decreed, are believed to govern the behavior of not only everything in the universe, but the form of the universe itself. However, this traditional concept of physics as a universal governance is at odds with our modern theories of quantum mechanics and relativity, which place the observer and information in a central role. In this talk, I aim to rethink the foundations and attempt to build physics from the bottom up based on a very simple foundational …

A Bijective Proof Of A Factorization Formula For Specialized Macdonald Polynomials, Nicholas A. Loehr, Elizabeth Niese

Elizabeth Niese

Let μ and ν = (ν 1, . . . , ν k ) be partitions such that μ is obtained from ν by adding m parts of sizer. Descouens and Morita proved algebraically that the modified Macdonald polynomials H~μ(X;q,t) satisfy the identity H~μ=H~νH~(rm) when the parameter t is specialize to an mth root of unity. Descouens, Morita, and Numata proved this formula bijectively when r ≤ ν k and r∈{1,2}. This note gives a bijective proof of the formula for all r ≤ ν k .

New Combinatorial Formulations Of The Shuffle Conjecture, Nicholas A. Loehr, Elizabeth Niese

Elizabeth Niese

The shuffle conjecture (due to Haglund, Haiman, Loehr, Remmel, and Ulyanov) provides a combinatorial formula for the Frobenius series of the diagonal harmonics module DHn, which is the symmetric function∇(en). This formula is a sum over all labeled Dyck paths of terms built from combinatorial statistics called area, dinv, and IDes. We provide three new combinatorial formulations of the shuffle conjecture based on other statistics on labeled paths, parking functions, and related objects. Each such reformulation arises by introducing an appropriate new definition of the inverse descent set. Analogous results are proved for the higher-order shuffle conjecture involving ∇m(en). We …

A New Recursion For Three-Column Combinatorial Macdonald Polynomials, Elizabeth Niese

Elizabeth Niese

The Hilbert series of the Garsia–Haiman module Mμ can be described combinatorially as the generating function of certain fillings of the Ferrers diagram of μ where μ is an integer partition of n . Since there are n ! fillings that generate , it is desirable to find recursions to reduce the number of fillings that need to be considered when computing combinatorially. In this paper, we present a combinatorial recursion for the case where μ is an n by 3 rectangle. This allows us to reduce the number of fillings under consideration from (3n)! to (3n)!/(3!nn!).

Fibonacci Number Of The Tadpole Graph, Joe Demaio, John Jacobson

Faculty and Research Publications

In 1982, Prodinger and Tichy defined the Fibonacci number of a graph G to be the number of independent sets of the graph G. They did so since the Fibonacci number of the path graph Pn is the Fibonacci number F(n+2) and the Fibonacci number of the cycle graph Cn is the Lucas number Ln. The tadpole graph Tn,k is the graph created by concatenating Cn and Pk with an edge from any vertex of Cn to a pendant of Pk for integers n=3 and k=0. This paper establishes formulae and identities for the Fibonacci number of the tadpole graph …

Impacts Of Climate Change On The Evolution Of The Electrical Grid, Melissa Ree Allen

Doctoral Dissertations

Maintaining interdependent infrastructures exposed to a changing climate requires understanding 1) the local impact on power assets; 2) how the infrastructure will evolve as the demand for infrastructure changes location and volume and; 3) what vulnerabilities are introduced by these changing infrastructure topologies. This dissertation attempts to develop a methodology that will a) downscale the climate direct effect on the infrastructure; b) allow population to redistribute in response to increasing extreme events that will increase under climate impacts; and c) project new distributions of electricity demand in the mid-21^st century.

The research was structured in three parts. The first …

Antimagic-Type Labelings, Sogol Jahanbekam

Faculty Publications

No abstract provided.

Deconstructing The Welch Equation Using P-Adic Methods, Abigail Mann, Adelyn Yeoh

Mathematical Sciences Technical Reports (MSTR)

The Welch map x -> g^x-1+c is similar to the discrete exponential map x -> g^x, which is used in many cryptographic applications including the ElGamal signature scheme. This paper analyzes the number of solutions to the Welch equation: g^x-1+c = x (mod p^e) where p is a prime, and looks at other patterns of the equation that could possibly exploited in a similar cryptographic system. Since the equation is modulo p^e, where p is a prime number, p-adic methods of analysis are used in counting the number of solutions modulo p …

Deconstructing The Welch Equation Using P-Adic Methods, Abigail Mann, Adelyn Yeoh

Rose-Hulman Undergraduate Research Publications

The Welch map x -> g^x-1+c is similar to the discrete exponential map x -> g^x, which is used in many cryptographic applications including the ElGamal signature scheme. This paper analyzes the number of solutions to the Welch equation: g^x-1+c = x (mod p^e) where p is a prime, and looks at other patterns of the equation that could possibly exploited in a similar cryptographic system. Since the equation is modulo p^e, where p is a prime number, p-adic methods of analysis are used in counting the number of solutions modulo p …

How Do I Love Thee? Let Me Count The Ways For Syllabic Variation In Certain Poetic Forms, Mike Pinter

Journal of Humanistic Mathematics

The Dekaaz poetic form, similar to haiku with its constrained syllable counts per line, invites a connection between poetry and mathematics. Determining the number of possible Dekaaz variations leads to some interesting counting observations. We discuss two different ways to count the number of possible Dekaaz variations, one using a binary framework and the other approaching the count as an occupancy problem. The counting methods described are generalized to also count variations of other poetic forms with syllable counts specified, including haiku. We include Dekaaz examples and suggest a method that can be used to randomly generate a Dekaaz variation.

Exact Tests For Singular Network Data, Ian H. Dinwoodie, Kruti Pandya

Mathematics and Statistics Faculty Publications and Presentations

We propose methodology for exact statistical tests of hypotheses for models of network dynamics. The methodology formulates Markovian exponential families, then uses sequential importance sampling to compute expectations within basins of attraction and within level sets of a sufficient statistic for an over-dispersion model. Comparisons of hypotheses can be done conditional on basins of attraction. Examples are presented.

Reichenbach Fuzzy Set Of Transitivity, Samina Ashraf, Muhammad A. Javed

Applications and Applied Mathematics: An International Journal (AAM)

Fuzzy implicators are the basic ingredients of many applications. So it becomes essential to study the various features of an implicator before implementing it in any practical application. This paper discusses the properties of transitivity of a fuzzy relation on a given universe and measure of fuzzy transitivity defined in terms of the Reichenbach fuzzy implicator which is an s-implicator.

The Linear Cutwidth And Cyclic Cutwidth Of Complete N-Partite Graphs, Stephanie A. Creswell

Electronic Theses, Projects, and Dissertations

The cutwidth of different graphs is a topic that has been extensively studied. The basis of this paper is the cutwidth of complete n-partite graphs. While looking at the cutwidth of complete n-partite graphs, we strictly consider the linear embedding and cyclic embedding. The relationship between the linear cutwidth and the cyclic cutwidth is discussed and used throughout multiple proofs of different cases for the cyclic cutwidth. All the known cases for the linear and cyclic cutwidth of complete bipartite, complete tripartite, and complete n-partite graphs are highlighted.

The main focus of this paper is to expand …

A Note On Independent Sets In Graphs With Large Minimum Degree And Small Cliques, Jeremy Lyle

Faculty Publications

Graphs with large minimum degree containing no copy of a clique on r vertices (K_r) must contain relatively large independent sets. A classical result of Andrásfai, Erdös, and Sós implies that K_r-free graphs G with degree larger than ((3r − 7)/(3r − 4))|V(G)| must be (r − 1)-partite. An obvious consequence of this result is that the same degree threshold implies an independent set of order (1/(r − 1))|V(G)|. The following paper provides improved bounds on the minimum degree which would imply the …

An Injection From Standard Fillings To Parking Functions, Elizabeth Niese

Elizabeth Niese

The Hilbert series of the Garsia-Haiman module can be written as a generating function of standard fillings of Ferrers diagrams. It is conjectured by Haglund and Loehr that the Hilbert series of the diagonal harmonics can be written as a generating function of parking functions. In this paper we present a weight-preserving injection from standard fillings to parking functions for certain cases.

Permutation Groups And Puzzle Tile Configurations Of Instant Insanity Ii, Amanda N. Justus

Electronic Theses and Dissertations

The manufacturer claims that there is only one solution to the puzzle Instant Insanity II. However, a recent paper shows that there are two solutions. Our goal is to find ways in which we only have one solution. We examine the permutation groups of the puzzle and use modern algebra to attempt to fix the puzzle. First, we find the permutation group for the case when there is only one empty slot at the top. We then examine the scenario when we add an extra column or an extra row to make the game a 4 × 5 puzzle or …

Results On Edge-Colored Graphs And Pancyclicity, James Carraher

Department of Mathematics: Dissertations, Theses, and Student Research

This thesis focuses on determining when a graph with additional structure contains certain subgraphs, particularly circuits, cycles, or trees. The specific problems and presented results include a blend of many fundamental graph theory concepts such as edge-coloring, routing problems, decomposition problems, and containing cycles of various lengths. The three primary chapters in this thesis address the problems of finding eulerian circuits with additional restrictions, decomposing the edge-colored complete graph K_n into rainbow spanning trees, and showing a 4-connected claw-free and N(3,2,1)-free graph is pancyclic.

Adviser: Stephen G. Hartke

Very Cost Effective Domination In Graphs, Tony K. Rodriguez

Electronic Theses and Dissertations

A set S of vertices in a graph G=(V,E) is a dominating set if every vertex in V\S is adjacent to at least one vertex in S, and the minimum cardinality of a dominating set of G is the domination number of G. A vertex v in a dominating set S is said to be very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is very cost effective if every vertex in S is very cost effective. The minimum cardinality of a very cost effective dominating set of …

Polynomial Factoring Algorithms And Their Computational Complexity, Nicholas Cavanna

Honors Scholar Theses

Finite fields, and the polynomial rings over them, have many neat algebraic properties and identities that are very convenient to work with. In this paper we will start by exploring said properties with the goal in mind of being able to use said properties to efficiently irreducibly factorize polynomials over these fields, an important action in the fields of discrete mathematics and computer science. Necessarily, we must also introduce the concept of an algorithm’s speed as well as particularly speeds of basic modular and integral arithmetic opera- tions. Outlining these concepts will have laid the groundwork for us to introduce …

Positive Periodic Solutions For A Higher Order Functional Difference Equation, Jacob Johnson

Chancellor’s Honors Program Projects

No abstract provided.

Combinatorial And Algebraic Coding Techniques For Flash Memory Storage, Kathryn A. Haymaker

Department of Mathematics: Dissertations, Theses, and Student Research

Error-correcting codes are used to achieve reliable and efficient transmission when storing or sending information across a noisy channel. This thesis investigates a mathematical approach to coding techniques for storage devices such as flash memory storage, although many of the resulting codes and coding schemes can be applied in other contexts. The main contributions of this work include the design of efficient codes and decoding algorithms using discrete structures such as graphs and finite geometries, and developing a variety of strategies for adapting codes to a multi-level setting.

Information storage devices are prone to errors over time, and the frequency …

New Combinatorial Formulations Of The Shuffle Conjecture, Nicholas A. Loehr, Elizabeth Niese

Mathematics Faculty Research

The shuffle conjecture (due to Haglund, Haiman, Loehr, Remmel, and Ulyanov) provides a combinatorial formula for the Frobenius series of the diagonal harmonics module DH_n, which is the symmetric function∇(e_n). This formula is a sum over all labeled Dyck paths of terms built from combinatorial statistics called area, dinv, and IDes. We provide three new combinatorial formulations of the shuffle conjecture based on other statistics on labeled paths, parking functions, and related objects. Each such reformulation arises by introducing an appropriate new definition of the inverse descent set. Analogous results are proved for the higher-order shuffle …

On The Dynamic Coloring Of Cartesian Product Graphs., Saieed Akbari, Maryam Ghanbari, S. Jahanbekam

Faculty Publications

No abstract provided.