Discrete Mathematics and Combinatorics Commons^™

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 …

Á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 …

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.

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.

Global Supply Sets In Graphs, Christian G. Moore

Electronic Theses and Dissertations

For a graph G=(V,E), a set S⊆V is a global supply set if every vertex v∈V\S has at least one neighbor, say u, in S such that u has at least as many neighbors in S as v has in V \S. The global supply number is the minimum cardinality of a global supply set, denoted γgs (G). We introduce global supply sets and determine the global supply number for selected families of graphs. Also, we give bounds on the global supply number for general graphs, trees, and grid graphs.

Completing Partial Latin Squares With One Nonempty Row, Column, And Symbol, Jaromy Kuhl, Michael W. Schroeder

Mathematics Faculty Research

Let r,c,s ∈{1,2,…,n} and let PP be a partial latin square of order n in which each nonempty cell lies in row r, column c, or contains symbol s. We show that if n ∉ {3, 4, 5} and row r, column c, and symbol s can be completed in P, then a completion of P exists. As a consequence, this proves a conjecture made by Casselgren and Häggkvist. Furthermore, we show exactly when row r, column c, and symbol s can be completed.

The Chromatic Number Of The Square Of Subcubic Planar Graphs, Stephen Hartke, Sogol Jahanbekam, Brent Thomas

Faculty Publications

Wegner conjectured in 1977 that the square of every planar graph with maximum degree at most 3 is 7-colorable. We prove this conjecture using the discharging method and computational techniques to verify reducible configurations.

Two Generalizations Of The Filippov Operation, Menevse Eryuzlu

Masters Theses & Specialist Projects

The purpose of this thesis is to generalize Filippov's operation, and to get more useful results. It includes two main parts: The C-Filippov operation for the finite and countable cases and the Filippov operation with different measures. In the first chapter, we give brief information about the importance of Filippov's operation, our goal and the ideas behind our generalizations. In the second chapter, we give some sufficient background notes. In the third chapter, we introduce the Filippov operation, explain how to calculate the Filippov of a function and give some sufficient properties of it. In the fourth chapter, we introduce …

Generalized Splines On Arbitrary Graphs, Simcha Gilbert, Julianna Tymoczko, Shira Viel

Mathematics Sciences: Faculty Publications

Let G be a graph whose edges are labeled by ideals of a commutative ring. We introduce a generalized spline, which is a vertex labeling of G by elements of the ring so that the difference between the labels of any two adjacent vertices lies in the corresponding edge ideal. Generalized splines arise naturally in combinatorics (algebraic splines of Billera and others) and in algebraic topology (certain equivariant cohomology rings, described by Goresky, Kottwitz, and MacPherson, among others). The central question of this paper asks when an arbitrary edge-labeled graph has nontrivial generalized splines. The answer is “always”, and we …

Combinatorial Descriptions Of The Crystal Structure On Certain Pbw Bases (Extended Abstract), Ben Salisbury, Adam Schultze, Peter Tingley

Mathematics and Statistics: Faculty Publications and Other Works

Lusztig's theory of PBW bases gives a way to realize the infinity crystal for any simple complex Lie algebra where the underlying set consists of Kostant partitions. In fact, there are many different such realizations, one for each reduced expression for the longest element of the Weyl group. There is an algorithm to calculate the actions of the crystal operators, but it can be quite complicated. For ADE types, we give conditions on the reduced expression which ensure that the corresponding crystal operators are given by simple combinatorial bracketing rules. We then give at least one reduced expression satisfying our …