Discrete Mathematics and Combinatorics Commons^™

Nested (2,R)-Regular Graphs And Their Network Properties., Josh Daniel Brooks

Electronic Theses and Dissertations

A graph G is a (t, r)-regular graph if every collection of t independent vertices is collectively adjacent to exactly r vertices. If a graph G is (2, r)-regular where p, s, and m are positive integers, and m ≥ 2, then when n is sufficiently large, then G is isomorphic to G = K_s+mK_p, where 2(p-1)+s = r. A nested (2,r)-regular graph is constructed by replacing selected cliques with a (2,r)-regular graph and joining the vertices of the peripheral cliques. For …

Global Domination Stable Graphs, Elizabeth Marie Harris

Electronic Theses and Dissertations

A set of vertices S in a graph G is a global dominating set (GDS) of G if S is a dominating set for both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We explore the effects of graph modifications on the global domination number. In particular, we explore edge removal, edge addition, and vertex removal.

A Survey Of Classical And Recent Results In Bin Packing Problem, Yoga Jaideep Darapuneni

UNLV Theses, Dissertations, Professional Papers, and Capstones

In the classical bin packing problem one receives a sequence of n items 1, 2,..., n with sizes s1, s2, . . . ,sn where each item has a fixed size in (0, 1]. One needs to find a partition of the items into sets of size1, called bins, so that the number of sets in the partition is minimized and the sum of the sizes of the pieces assigned to any bin does not exceed its capacity. This combinatorial optimization problem which is NP hard has many variants as well as online and offline versions of the problem. Though …

Generating Minimal T-Wise Test Suites, Luis C. Gutierrez, Carlos Nieto, Francisco Zapata, Martine Ceberio

COURI Symposium Abstracts, Summer 2012

As the use of computing devices increases every day, users rely on the adequate functioning of software. When software is not tested properly, it can yield erroneous information or a complete failure of the system. The NIST estimates that defective software cost the United States economy close to $60 billion a year. Therefore, there is a need to develop software testing techniques that are time and cost effective. Fully testing software under all possible combinations of parameters values cannot be reduced. However, testing can focus on covering all combinations of subsets of parameters and empirical data shows that doing so …

The Weak Discrepancy And Linear Extension Diameter Of Grids And Other Posets, Katherine Victoria Johnson

Department of Mathematics: Dissertations, Theses, and Student Research

A linear extension of a partially ordered set is simply a total ordering of the poset that is consistent with the original ordering. The linear extension diameter is a measure of how different two linear extensions could be, that is, the number of pairs of elements that are ordered differently by the two extensions. In this dissertation, we calculate the linear extension diameter of grids. This also gives us a nice characterization of the linear extensions that are the farthest from each other, and allows us to conclude that grids are diametrally reversing.

A linear extension of a poset might …

Q -Analogs Of Identities Involving Harmonic Numbers And Binomial Coefficients, Toufik Mansour, Mark Shattuck, Chunwei Song

Applications and Applied Mathematics: An International Journal (AAM)

Recently, McCarthy presented two algebraic identities involving binomial coefficients and harmonic numbers, one of which generalizes an identity used to prove the Apéry number supercongruence. In 2008, Prodinger provided human proofs of identities initially obtained by Osburn and Schneider using the computer program Sigma. In this paper, we establish q -analogs of a fair number of the identities appearing in McCarthy (Integers 11 (2011): A37) and Prodinger (Integers 8 (2008): A10) by making use of q -partial fractions.

Cyclic Matching Sequencibility Of Graphs, Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder

Mathematics Faculty Research

We define the cyclic matching sequencibility of a graph to be the largest integer d such that there exists a cyclic ordering of its edges so that every d consecutive edges in the cyclic ordering form a matching. We show that the cyclic matching sequencibility of K_2m and K_2m+1 equals m − 1.

A Simple Bijection Between Standard 3×N Tableaux And Irreducible Webs For ����3, Julianna Tymoczko

Mathematics Sciences: Faculty Publications

Combinatorial spiders are a model for the invariant space of the tensor product of representations. The basic objects, webs, are certain directed planar graphs with boundary; algebraic operations on representations correspond to graph-theoretic operations on webs. Kuperberg developed spiders for rank 2 Lie algebras and ����₂. Building on a result of Kuperberg’s, Khovanov-Kuperberg found a recursive algorithm giving a bijection between standard Young tableaux of shape 3 × n and irreducible webs for ����₃whose boundary vertices are all sources. In this paper, we give a simple and explicit map from standard Young tableaux of shape 3 …

Liar's Domination In Grid Graphs, Christopher Kent Sterling

Electronic Theses and Dissertations

As introduced by Slater in 2008, liar's domination provides a way of modeling protection devices where one may be faulty. Assume each vertex of a graph G is the possible location for an intruder such as a thief. A protection device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v] and identify at which vertex in N[v] the intruder is located. A dominating set is required to identify any intruder's location in the graph G, and if any one device can fail to …

Preferential Arrangement Containment In Strict Superpatterns, Martha Louise Liendo

Electronic Theses and Dissertations

Most results on pattern containment deal more directly with pattern avoidance, or the enumeration and characterization of strings which avoid a given set of patterns. Little research has been conducted regarding the word size required for a word to contain all patterns of a given set of patterns. The set of patterns for which containment is sought in this thesis is the set of preferential arrangements of a given length. The term preferential arrangement denotes strings of characters in which repeated characters are allowed, but not necessary. Cardinalities for sets of all preferential arrangements of given lengths and alphabet sizes …

The Rook-Brauer Algebra, Elise G. Delmas

Mathematics, Statistics, and Computer Science Honors Projects

We introduce an associative algebra RB_k(x) that has a basis of rook-Brauer diagrams. These diagrams correspond to partial matchings on 2k vertices. The rook-Brauer algebra contains the group algebra of the symmetric group, the Brauer algebra, and the rook monoid algebra as subalgebras. We show that the basis of RB_k(x) is generated by special diagrams s_i, t_i (1 <= i < k) and p_j (1 <= j <= k), where the s_i are the simple transpositions that generated the symmetric group S_k, the t_i are the "contraction maps" which generate the …

Generating Minimal Pair-Wise Covering Test Suites, Luis C. Gutierrez ^, Martine Ceberio *

COURI Symposium Abstracts, Spring 2012

Software is ubiquitous and needs to be reliable. Software testing therefore plays an important role in software development. Proper testing a software system informs about its quality and reliability so as to prevent unexpected behavior during system execution. One of the methods to prevent failures consists in testing a system under different input values, but when all possible input values are tested, an impractical number of test cases might result. In software testing, pair-wise testing is a combinatorial technique which uses combination of pair input values to generate test cases. Using pair-wise testing dramatically reduces the number of test cases, …

Combinatorics Using Computational Methods, Derrick Stolee

Department of Mathematics: Dissertations, Theses, and Student Research

Computational combinatorics involves combining pure mathematics, algorithms, and computational resources to solve problems in pure combinatorics. This thesis provides a theoretical framework for combinatorial search, which is then applied to several problems in combinatorics. Some results in space-bounded computational complexity are also presented.

The 1, 2-Conjecture For Graphs With Relatively Small Chromatic Number, Sogol Jahanbekam, Douglas West

Faculty Publications

No abstract provided.

Exploring The On-Line Partitioning Of Posets Problem, Leah F. Rosenbaum

Scripps Senior Theses

One question relating to partially ordered sets (posets) is that of partitioning or dividing the poset's elements into the fewest number of chains that span the poset. In 1950, Dilworth established that the width of the poset - the size of the largest set composed only of incomparable elements - is the minimum number of chains needed to partition that poset. Such a bound in on-line partitioning has been harder to establish, and work has evalutated classes of posets based on their width. This paper reviews the theorems that established val(2)=5 and illustrates them with examples. It also covers some …

Session D-3: Discrete Mathematics: A Great Curriculum Connector, Donald Porzio

Professional Learning Day

Many topics that fall under the umbrella of Discrete Mathematics cut across the traditional high school curriculum areas of algebra, geometry, and pre-calculus. Come try some classroom-ready hands-on Discrete Mathematics activities that illustrate the true interconnectedness of mathematics.

Fixed Points And Excedances In Restricted Permutations, Sergi Elizalde

Dartmouth Scholarship

Using an unprecedented technique involving diagonals of non-rational generating functions, we prove that among the permutations of length $n$ with $i$ fixed points and $j$ excedances, the number of 321-avoiding ones equals the number of 132-avoiding ones, for any given $i,j$. Our theorem generalizes a result of Robertson, Saracino and Zeilberger. Even though bijective proofs have later been found by the author jointly with Pak and with Deutsch, this paper contains the original analytic proof that was presented at FPSAC 2003.

Complete Multipartite Graphs And The Relaxed Coloring Game, Charles Dunn

Faculty Publications

Let k be a positive integer, d be a nonnegative integer, and G be a finite graph. Two players, Alice and Bob, play a game on G by coloring the uncolored vertices with colors from a set X of k colors. At all times, the subgraph induced by a color class must have maximum degree at most d. Alice wins the game if all vertices are eventually colored; otherwise, Bob wins. The least k such that Alice has a winning strategy is called the d-relaxed game chromatic number of G, denoted χ _g^d (G). …

The Minimum Of The Maximum Rectilinear Crossing Numbers Of Small Cubic Graphs, Matthew Alpert, Jens-P. Bode, Elie Feder, Heiko Harborth

Publications and Research

Here we consider the minimum of the maximum rectilin­ear crossing numbers for all d-regular graphs of order n. The case of connected graphs only is investigated also. For d = 3 exact values are determined for n are less than or equal to 12 and some estimations are given in general.

Semigroup As Graphs, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

In this book the authors study the zero divisor graph and unit graph of a semigroup. The zero divisor graphs of semigroups Zn under multiplication is studied and characterized.