Physical Sciences and Mathematics Commons^™

Cost Effective Domination In Graphs, Tabitha Lynn Mccoy

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. A vertex v in a dominating set S is said to be it cost effective if it is adjacent to at least as many vertices in V \ S as it is in S. A dominating set S is cost effective if every vertex in S is cost effective. The minimum cardinality of a cost effective dominating set of G is the cost …

K-Total Product Cordial Labelling Of Graphs, R. Ponraj, M. Sundaram, M. Sivakumar

Applications and Applied Mathematics: An International Journal (AAM)

In this paper we introduce the k-Total Product cordial labelling of graphs. Also we investigate the 3-Total Product cordial labelling behaviour of some standard graphs.

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

Mathematics Faculty Research

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~(r^m)

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 .

Generalizations Of Two Statistics On Linear Tilings, Toufik Mansour, Mark Shattuck

Applications and Applied Mathematics: An International Journal (AAM)

In this paper, we study generalizations of two well-known statistics on linear square-and-domino tilings by considering only those dominos whose right half covers a multiple of 􀝇, where 􀝇 is a fixed positive integer. Using the method of generating functions, we derive explicit expressions for the joint distribution polynomials of the two statistics with the statistic that records the number of squares in a tiling. In this way, we obtain two families of q -generalizations of the Fibonacci polynomials. When 􀝇 􀵌 1, our formulas reduce to known results concerning previous statistics. Special attention is payed to the case 􀝇 …

Hamilton Decompositions Of Certain 6-Regular Cayley Graphs On Abelian Groups With A Cyclic Subgroup Of Index Two, Erik E. Westlund

Faculty and Research Publications

Alspach conjectured that every connected Cayley graph of even valency on a finite Abelian group is Hamilton-decomposable. Using some techniques of Liu, this article shows that if A is an Abelian group of even order with a generating set {a,b}, and A contains a subgroup of index two, generated by c, then the 6-regular Cayley graph is Hamilton-decomposable.

There Is No Triangulation Of The Torus With Vertex Degrees 5, 6, . . ., 6, 7 And Related Results: Geometric Proofs For Combinatorial Theorems, Ivan Izmestiev, Robert B. Kusner, Günter Rote, Boris Springborn, John M. Sullivan

Robert Kusner

There is no 5,7-triangulation of the torus, that is, no triangulation with exactly two exceptional vertices, of degree 5 and 7. Similarly, there is no 3,5-quadrangulation. The vertices of a 2,4-hexangulation of the torus cannot be bicolored. Similar statements hold for 4,8-triangulations and 2,6-quadrangulations. We prove these results, of which the first two are known and the others seem to be new, as corollaries of a theorem on the holonomy group of a euclidean cone metric on the torus with just two cone points. We provide two proofs of this theorem: One argument is metric in nature, the other relies …

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.

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 …

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 …

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.

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 …

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.

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 …

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 …

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 …

Generalized Branching In Circle Packing, James Russell Ashe

Doctoral Dissertations

Circle packings are configurations of circle with prescribed patterns of tangency. They relate to a surprisingly diverse array of topics. Connections to Riemann surfaces, Apollonian packings, random walks, Brownian motion, and many other topics have been discovered. Of these none has garnered more interest than circle packings' relationship to analytical functions. With a high degree of faithfulness, maps between circle packings exhibit essentially the same geometric properties as seen in classical analytical functions. With this as motivation, an entire theory of discrete analytic function theory has been developed. However limitations in this theory due to the discreteness of circle packings …

On The Number Of Tilings Of A Square By Rectangles, Timothy Michaels

Chancellor’s Honors Program Projects

No abstract provided.

Extremal Problems For Roman Domination, E. W. Chambers, W. Kinnersley, N. Prince, D. B. West

Noah Prince

A Roman dominating function of a graph G is a labeling f: V(G) →{0,1,2} such that every vertex with a label 0 has a neighbor with label 2. The Roman domination number γ_R(G) of G is the minimum of ∑_ʋϵV(G)f(v) over such functions. Let G be a connected n-vertex graph. We prove that γ_R(G) ≤ 4n/5, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for γ_R(G) + …

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.

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 …

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

Faculty Publications

No abstract provided.

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.

Finite Factors Of Bernoulli Schemes And Distinguishing Labelings Of Directed Graphs, Andrew Lazowski, Stephen M. Shea

Mathematics Faculty Publications

A labeling of a graph is a function from the vertices of the graph to some finite set. In 1996, Albertson and Collins defined distinguishing labelings of undirected graphs. Their definition easily extends to directed graphs. Let G be a directed graph associated to the k -block presentation of a Bernoulli scheme X . We determine the automorphism group of G , and thus the distinguishing labelings of G . A labeling of G defines a finite factor of X . We define demarcating labelings and prove that demarcating labelings define finitarily Markovian finite factors of X . We use …

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). …

Introduction Aux Méthodes D’Intégrale De Chemin Et Applications, Nour-Eddiine Fahssi

Nour-Eddine Fahssi

These lecture notes are based on a master course given at University Hassan II - Agdal in spring 2012.

On A Pair Of Identities From Ramanujan's Lost Notebook, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

Using a pair of two variable series-product identities recorded by Ramanujan in the lost notebook as inspiration, we find some new identities of similar type. Each identity immediately implies an infinite family of Rogers-Ramanujan type identities, some of which are well-known identities from the literature. We also use these identities to derive some general identities for integer partitions.

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.

Innovative Uses Of Matrices, Florentin Smarandache, W.B. Vasantha Kandasamy, Indra Venkatbabu

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors bring out the innovative applications of matrices defined, described and developed by them. Here they do not include the natural product on matrices newly described and defined by them in the book on ‘natural product ×n on matrices’.

This book is organized into seven chapters. The first one is introductory in nature. In the second chapter authors give the unique and new way of analyzing the data which is time dependent. We construct three types of matrices called Average Time Dependent data matrix (ATD matrix), Refined Time Dependent Data matrix (RTD matrix) and Combined Effective Time …