Discrete Mathematics and Combinatorics Commons^™

An Improvement In The Two-Packing Bound Related To Vizing's Conjecture, Kimber Wolff

Theory and Applications of Graphs

Vizing's conjecture states that the domination number of the Cartesian product of graphs is at least the product of the domination numbers of the two factor graphs. In this note we improve the recent bound of Breŝar by applying a technique of Zerbib to show that for any graphs G and H, γ(G x H)≥ γ (G) 2/3(γ(H)-ρ(H)+1), where γ is the domination number, ρ is the 2-packing number, and x is the Cartesian product.

On A Vizing-Type Integer Domination Conjecture, Elliot Krop, Randy R. Davila

Theory and Applications of Graphs

Given a simple graph G, a dominating set in G is a set of vertices S such that every vertex not in S has a neighbor in S. Denote the domination number, which is the size of any minimum dominating set of G, by γ(G). For any integer k ≥ 1, a function f : V (G) → {0, 1, . . ., k} is called a {k}-dominating function if the sum of its function values over any closed neighborhood is at least k. The weight of a {k}-dominating function is the sum of its values over all …

H-Discrete Fractional Model Of Tumor Growth And Anticancer Effects Of Mono And Combination Therapies, Kamala Dadashova

Masters Theses & Specialist Projects

In this thesis, we focus on h–discrete and h–discrete fractional representation of a pharmacokinetics-pharmacodynamics (PK-PD) model which describes tumor growth considering time on hNa, where h>0. First, we introduce some definitions, lemmas and theorems on both h–discrete and h–discrete fractional calculus in the preliminary section. In Chapter 3, we work on the PD model with delay by exam ining nabla h–discrete equations and nabla h–discrete fractional equations as well as variation of constants formulas, accordingly. We introduce our model and solve it using theorems we proved in the last section of the indicated chapter. When we do simulation for …

Extremal Problems On Induced Graph Colorings, James Hallas

Dissertations

Graph coloring is one of the most popular areas of graph theory, no doubt due to its many fascinating problems and applications to modern society, as well as the sheer mathematical beauty of the subject. As far back as 1880, in an attempt to solve the famous Four Color Problem, there have been numerous examples of certain types of graph colorings that have generated other graph colorings of interest. These types of colorings only gained momentum a century later, however, when in the 1980s, edge colorings were studied that led to vertex colorings of various types, led by the introduction …

Recursive Formulas For Beans Functions Of Graphs, Kengo Enami, Seiya Negami

Theory and Applications of Graphs

In this paper, we regard each edge of a connected graph G as a line segment having a unit length, and focus on not only the "vertices" but also any "point" lying along such a line segment. So we can define the distance between two points on G as the length of a shortest curve joining them along G. The beans function B_G(x) of a connected graph G is defined as the maximum number of points on G such that any pair of points have distance at least x>0. We shall show a recursive formula for …

On Selected Subclasses Of Matroids, Tara Elizabeth Fife

LSU Doctoral Dissertations

Matroids were introduced by Whitney to provide an abstract notion of independence.

In this work, after giving a brief survey of matroid theory, we describe structural results for various classes of matroids. A connected matroid $M$ is unbreakable if, for each of its flats $F$, the matroid $M/F$ is connected%or, equivalently, if $M^*$ has no two skew circuits. . Pfeil showed that a simple graphic matroid $M(G)$ is unbreakable exactly when $G$ is either a cycle or a complete graph. We extend this result to describe which graphs are the underlying graphs of unbreakable frame matroids. A laminar family is …

A Mathematical Model Of Speeding, Jared Ott, Xavier Pérez Giménez

Honors Theses

Crime is often regarded as nonsensical, impulsive, and irrational. These conjectures are pointed, though conversation about the pros and cons of crime does not happen often. People point to harsh fines, jail times, and life restrictions as their reason for judgement, stating that the trade-offs are far too unbalanced to participate in illicit activity. Yet, everyday people commit small crimes, sometimes based on hedonistic desires, other times based on a rational thought process.

Speeding seems to be one of those that almost all people commit at least once during their life. Our work hopes to make an incremental improvement on …

Triangles In Ks-Saturated Graphs With Minimum Degree T, Craig Timmons, Benjamin Cole, Albert Curry, David Davini

Theory and Applications of Graphs

For n ≥ 15, we prove that the minimum number of triangles in an n-vertex K₄-saturated graph with minimum degree 4 is exactly 2n-4, and that there is a unique extremal graph. This is a triangle version of a result of Alon, Erdos, Holzman, and Krivelevich from 1996. Additionally, we show that for any s > r ≥ 3 and t ≥ 2 (s-2)+1, there is a K_s-saturated n-vertex graph with minimum degree t that has \binom{ s-2}{r-1}2^{r-1} n + c_{s,r,t} copies of K_r. This shows that …

Math 220p Foundations Of Mathematics, Nicholas Vlamis

Open Educational Resources

No abstract provided.

From Dyck Paths To Standard Young Tableaux, Juan B. Gil, Peter R. W. Mcnamara, Jordan O. Tirrell, Michael D. Weiner

Faculty Journal Articles

We present nine bijections between classes of Dyck paths and classes of standard Young tableaux (SYT). In particular, we consider SYT of flag and rectangular shapes, we give Dyck path descriptions for certain SYT of height at most 3, and we introduce a special class of labeled Dyck paths of semilength n that is shown to be in bijection with the set of all SYT with n boxes. In addition, we present bijections from certain classes of Motzkin paths to SYT. As a natural framework for some of our bijections, we introduce a class of set partitions which in some …

Consecutive Prime And Highly Total Prime Labeling In Graphs, Robert Scholle

Rose-Hulman Undergraduate Mathematics Journal

This paper examines the graph-theoretical concepts of consecutive prime labeling and highly total prime labeling. These are variations on prime labeling, introduced by Tout, Dabboucy, and Howalla in 1982. Consecutive prime labeling is defined here for the first time. Consecutive prime labeling requires that the labels of vertices in a graph be relatively prime to the labels of all adjacent vertices as well as all incident edges. We show that all paths, cycles, stars, and complete graphs have a consecutive prime labeling and conjecture that all simple connected graphs have a consecutive prime labeling.

This paper also expands on work …

Combinatorial Identities On Multinomial Coefficients And Graph Theory, Seungho Lee

Rose-Hulman Undergraduate Mathematics Journal

We study combinatorial identities on multinomial coefficients. In particular, we present several new ways to count the connected labeled graphs using multinomial coefficients.

Graham's Pebbling Conjecture Holds For The Product Of A Graph And A Sufficiently Large Complete Graph, Nopparat Pleanmani

Theory and Applications of Graphs

For connected graphs G and H, Graham conjectured that π(G □ H) ≤ π(G) π(H) where π(G), π (H), and π(G □ H) are the pebbling numbers of G, H, and the Cartesian product G □ H, respectively. In this paper, we show that the inequality holds when H is a complete graph of sufficiently large order in terms of graph parameters of G.

A Cool Brisk Walk Through Discrete Mathematics, Stephen Davies

Computer Science Articles

A Cool Brisk Walk Through Discrete Mathematics - and its companion site "allthemath" - are completely-and-forever-free-and-open-source educational materials dedicated to the mathematics that budding computer science practitioners actually need to know. They feature the fun and addictive teaching of award-winning lecturer Dr. Stephen Davies of the University of Mary Washington in Fredericksburg, Virginia!

On The Ranks Of String C-Group Representations For Symplectic And Orthogonal Groups, Peter A. Brooksbank

Faculty Journal Articles

We determine the ranks of string C-group representations of 4-dimensional projective symplectic groups over a finite field, and comment on those of higher-dimensional symplectic and orthogonal groups.

A Mathematical Analysis Of The Game Of Santorini, Carson Clyde Geissler

Senior Independent Study Theses

Santorini is a two player combinatorial board game. Santorini bears resemblance to the graph theory game of Geography, a game of moving and deleting vertices on a graph. We explore Santorini with game theory, complexity theory, and artificial intelligence. We present David Lichtenstein’s proof that Geography is PSPACE-hard and adapt the proof for generalized forms of Santorini. Last, we discuss the development of an AI built for a software implementation of Santorini and present a number of improvements to that AI.

On The Mysteries Of Interpolation Jack Polynomials, Havi Ellers

HMC Senior Theses

Interpolation Jack polynomials are certain symmetric polynomials in N variables with coefficients that are rational functions in another parameter k, indexed by partitions of length at most N. Introduced first in 1996 by F. Knop and S. Sahi, and later studied extensively by Sahi, Knop-Sahi, and Okounkov-Olshanski, they have interesting connections to the representation theory of Lie algebras. Given an interpolation Jack polynomial we would like to differentiate it with respect to the variable k and write the result as a linear combination of other interpolation Jack polynomials where the coefficients are again rational functions in k. In this …

A Discrete Analogue For The Poincaré-Hopf Theorem, Savana Ammons

HMC Senior Theses

In this thesis, we develop a discrete analogue to the Poincaré–Hopf Theorem. We define the notion of a vector field on a graph, and establish an index theory for such a field. Specifically, we create well-defined indices for the nodes and “cells" formed by a planar graph. Then, we show that the sum of these indices remains constant for certain types of planar graphs, regardless of the discrete vector fields they have.

An Exploration Of Combinatorial Interpretations For Fibonomial Coefficients, Richard Shapley

HMC Senior Theses

We can define Fibonomial coefficients as an analogue to binomial coefficients as F(n,k) = F_nF_n-1 … F­_n-k+1 / F­_kF_k-­1…F₁, where F_n represents the nth Fibonacci number. Like binomial coefficients, there are many identities for Fibonomial coefficients that have been proven algebraically. However, most of these identities have eluded combinatorial proofs.

Sagan and Savage (2010) first presented a combinatorial interpretation for these Fibonomial coefficients. More recently, Bennett et al. (2018) provided yet another interpretation, that is perhaps more tractable. However, there still has been little progress towards using these interpretations …

Phylogenetic Networks And Functions That Relate Them, Drew Scalzo

Williams Honors College, Honors Research Projects

Phylogenetic Networks are defined to be simple connected graphs with exactly n labeled nodes of degree one, called leaves, and where all other unlabeled nodes have a degree of at least three. These structures assist us with analyzing ancestral history, and its close relative - phylogenetic trees - garner the same visualization, but without the graph being forced to be connected. In this paper, we examine the various characteristics of Phylogenetic Networks and functions that take these networks as inputs, and convert them to more complex or simpler structures. Furthermore, we look at the nature of functions as they relate …