Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons

Open Access. Powered by Scholars. Published by Universities.®

960 Full-Text Articles 1,121 Authors 104,022 Downloads 95 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

960 full-text articles. Page 31 of 36.

Nested (2,R)-Regular Graphs And Their Network Properties., Josh Daniel Brooks 2012 East Tennessee State University

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 = Ks+mKp, 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 example, in a nested 's' graph when n = s ...


Global Domination Stable Graphs, Elizabeth Marie Harris 2012 East Tennessee State University

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 2012 University of Nevada, Las Vegas

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 problem is ...


Bipartizing Fullerenes, Zdeněk Dvořák, Bernard Lidicky, Riste Škrekovskib 2012 Charles University

Bipartizing Fullerenes, Zdeněk Dvořák, Bernard Lidicky, Riste Škrekovskib

Bernard Lidický

A fullerene graph is a cubic bridgeless planar graph with twelve 5-faces such that all other faces are 6-faces. We show that any fullerene graph on vertices can be bipartized by removing edges. This bound is asymptotically optimal.


The Weak Discrepancy And Linear Extension Diameter Of Grids And Other Posets, Katherine Victoria Johnson 2012 University of Nebraska-Lincoln

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

Dissertations, Theses, and Student Research Papers in Mathematics

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


Parameters Related To Tree-Width, Zero Forcing, And Maximum Nullity Of A Graph, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, Leslie Hogben, Bryan Shader, P. van den Driessche, Hein van der Holst 2012 University of Tennessee, Chattanooga

Parameters Related To Tree-Width, Zero Forcing, And Maximum Nullity Of A Graph, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, Leslie Hogben, Bryan Shader, P. Van Den Driessche, Hein Van Der Holst

Mathematics Publications

Tree-width, and variants that restrict the allowable tree decompositions, play an important role in the study of graph algorithms and have application to computer science. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by a graph. We establish relationships between these parameters, including several Colin de Verdière type parameters, and introduce numerous variations, including the minor monotone floors and ceilings of some of these parameters. This leads to new graph parameters and to new characterizations of existing graph parameters. In particular, tree-width, largeur d'arborescence, path-width, and proper ...


Vertex And Edge Spread Of Zero Forcing Number, Maximum Nullity, And Minimum Rank Of A Graph, Christina J. Edholm, Leslie Hogben, My Huynh, Josh LaGrange, Darren D. Row 2012 Willamette University

Vertex And Edge Spread Of Zero Forcing Number, Maximum Nullity, And Minimum Rank Of A Graph, Christina J. Edholm, Leslie Hogben, My Huynh, Josh Lagrange, Darren D. Row

Mathematics Publications

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i not equal j) is nonzero whenever {i, j} is an edge in G and is zero otherwise; maximum nullity is taken over the same set of matrices. The zero forcing number is the minimum size of a zero forcing set of vertices and bounds the maximum nullity from above. The spread of a graph parameter at a vertex v or edge e of G is the difference between the value of the parameter on ...


On The Graph Complement Conjecture For Minimum Rank, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Hein van der Holst 2012 University of Tennessee, Chattanooga

On The Graph Complement Conjecture For Minimum Rank, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Hein Van Der Holst

Mathematics Publications

The minimum rank of a graph has been an interesting and well studied parameter investigated by many researchers over the past decade or so. One of the many unresolved questions on this topic is the so-called graph complement conjecture, which grew out of a workshop in 2006. This conjecture asks for an upper bound on the sum of the minimum rank of a graph and the minimum rank of its complement, and may be classified as a Nordhaus–Gaddum type problem involving the graph parameter minimum rank. The conjectured bound is the order of the graph plus two. Other variants ...


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

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

Mathematics and Statistics: 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 xxx2. 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 xxx3 whose boundary vertices are all sources. In this paper, we give a simple and explicit map from standard Young tableaux of shape 3 × n ...


Liar's Domination In Grid Graphs, Christopher Kent Sterling 2012 East Tennessee State University

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 detect ...


Preferential Arrangement Containment In Strict Superpatterns, Martha Louise Liendo 2012 East Tennessee State University

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 2012 Macalester College

The Rook-Brauer Algebra, Elise G. Delmas

Mathematics, Statistics, and Computer Science Honors Projects

We introduce an associative algebra RBk(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 RBk(x) is generated by special diagrams si, ti (1 <= i < k) and pj (1 <= j <= k), where the si are the simple transpositions that generated the symmetric group Sk, the ti are the "contraction maps" which generate the Brauer algebra Bk ...


On The Number Of Tilings Of A Square By Rectangles, Timothy Michaels 2012 University of Tennessee - Knoxville

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

Chancellor’s Honors Program Projects

No abstract provided.


Generalized Branching In Circle Packing, James Russell Ashe 2012 University of Tennessee, Knoxville

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


Extremal Problems For Roman Domination, E. W. Chambers, W. Kinnersley, N. Prince, D. B. West 2012 Illinois Mathematics and Science Academy

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) + γR() and γR(G)γR(), improving known results ...


Combinatorics Using Computational Methods, Derrick Stolee 2012 University of Nebraska-Lincoln

Combinatorics Using Computational Methods, Derrick Stolee

Dissertations, Theses, and Student Research Papers in Mathematics

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 2012 University of Illinois at Urbana–Champaign

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 2012 Scripps College

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


Session D-3: Discrete Mathematics: A Great Curriculum Connector, Donald Porzio 2012 Illinois Mathematics and Science Academy

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 2012 Dartmouth College

Fixed Points And Excedances In Restricted Permutations, Sergi Elizalde

Open Dartmouth: Faculty Open Access Articles

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.


Digital Commons powered by bepress