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

Discrete Mathematics and Combinatorics Commons

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

822 Full-Text Articles 963 Authors 73,100 Downloads 89 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

822 full-text articles. Page 1 of 29.

Integer-Antimagic Spectra Of Disjoint Unions Of Cycles, Wai Chee Shiu 2018 Hong Kong Baptist University

Integer-Antimagic Spectra Of Disjoint Unions Of Cycles, Wai Chee Shiu

Theory and Applications of Graphs

Let $A$ be a non-trivial abelian group. A simple graph $G = (V, E)$ is $A$-antimagic if there exists an edge labeling $f: E(G) \to A \setminus \{0\}$ such that the induced vertex labeling $f^+: V(G) \to A$, defined by $f^+(v) = \sum_{uv\in E(G)}f(uv)$, is injective. The integer-antimagic spectrum of a graph $G$ is the set IAM$(G) = \{k\;|\; G \textnormal{ is } \mathbb{Z}_k\textnormal{-antimagic and } k \geq 2\}$. In this paper, we determine the integer-antimagic spectra of disjoint unions of cycles.


An Efficient Algorithm To Test Forcibly-Connectedness Of Graphical Degree Sequences, Kai Wang 2018 Georgia Southern University

An Efficient Algorithm To Test Forcibly-Connectedness Of Graphical Degree Sequences, Kai Wang

Theory and Applications of Graphs

We present an algorithm to test whether a given graphical degree sequence is forcibly connected or not and prove its correctness. We also outline the extensions of the algorithm to test whether a given graphical degree sequence is forcibly $k$-connected or not for every fixed $k\ge 2$. We show through experimental evaluations that the algorithm is efficient on average, though its worst case run time is probably exponential. We also adapt Ruskey et al's classic algorithm to enumerate zero-free graphical degree sequences of length $n$ and Barnes and Savage's classic algorithm to enumerate graphical partitions of ...


Finite Asymptotic Clusters Of Metric Spaces, Viktoriia Bilet, Oleksiy Dovgoshey 2018 Institute of Applied Mathematics and Mechanics of NAS of Ukraine

Finite Asymptotic Clusters Of Metric Spaces, Viktoriia Bilet, Oleksiy Dovgoshey

Theory and Applications of Graphs

Let $(X, d)$ be an unbounded metric space and let $\tilde r=(r_n)_{n\in\mathbb N}$ be a sequence of positive real numbers tending to infinity. A pretangent space $\Omega_{\infty, \tilde r}^{X}$ to $(X, d)$ at infinity is a limit of the rescaling sequence $\left(X, \frac{1}{r_n}d\right).$ The set of all pretangent spaces $\Omega_{\infty, \tilde r}^{X}$ is called an asymptotic cluster of pretangent spaces. Such a cluster can be considered as a weighted graph $(G_{X, \tilde r}, \rho_{X})$ whose maximal cliques coincide with $\Omega_{\infty, \tilde r}^{X ...


A Computer-Aided Decomposition Of The Complete Digraph Into Orientations Of K4 − E With A Double Edge, Hanson Hao 2018 Illinois Mathematics and Science Academy

A Computer-Aided Decomposition Of The Complete Digraph Into Orientations Of K4 − E With A Double Edge, Hanson Hao

The International Student Science Fair 2018

The abstract is available as an Additional File.


Dimers On Cylinders Over Dynkin Diagrams And Cluster Algebras, Maitreyee Chandramohan Kulkarni 2018 Louisiana State University and Agricultural and Mechanical College

Dimers On Cylinders Over Dynkin Diagrams And Cluster Algebras, Maitreyee Chandramohan Kulkarni

LSU Doctoral Dissertations

This dissertation describes a general setting for dimer models on cylinders over Dynkin diagrams which in type A reduces to the well-studied case of dimer models on a disc. We prove that all Berenstein--Fomin--Zelevinsky quivers for Schubert cells in a symmetric Kac--Moody algebra give rise to dimer models on the cylinder over the corresponding Dynkin diagram. We also give an independent proof of a result of Buan, Iyama, Reiten and Smith that the corresponding superpotentials are rigid using the dimer model structure of the quivers.


Facial Unique-Maximum Colorings Of Plane Graphs With Restriction On Big Vertices, Bernard Lidicky, Kacy Messerschmidt, Riste Škrekovski 2018 Iowa State University

Facial Unique-Maximum Colorings Of Plane Graphs With Restriction On Big Vertices, Bernard Lidicky, Kacy Messerschmidt, Riste Škrekovski

Mathematics Publications

A facial unique-maximum coloring of a plane graph is a proper coloring of the vertices using positive integers such that each face has a unique vertex that receives the maximum color in that face. Fabrici and Göring (2016) proposed a strengthening of the Four Color Theorem conjecturing that all plane graphs have a facial unique-maximum coloring using four colors. This conjecture has been disproven for general plane graphs and it was shown that five colors suffice. In this paper we show that plane graphs, where vertices of degree at least four induce a star forest, are facially unique-maximum 4-colorable. This ...


Templates For Representable Matroids, Kevin Manuel Grace 2018 Louisiana State University and Agricultural and Mechanical College

Templates For Representable Matroids, Kevin Manuel Grace

LSU Doctoral Dissertations

The matroid structure theory of Geelen, Gerards, and Whittle has led to a hypothesis that a highly connected member of a minor-closed class of matroids representable over a finite field is a mild modification (known as a perturbation) of a frame matroid, the dual of a frame matroid, or a matroid representable over a proper subfield. They introduced the notion of a template to describe these perturbations in more detail. In this dissertation, we determine these templates for various classes and use them to prove results about representability, extremal functions, and excluded minors.

Chapter 1 gives a brief introduction to ...


Average Mixing Matrix Of Trees, Chris Godsil, Krystal Guo, John Sinkovic 2018 University of Waterloo

Average Mixing Matrix Of Trees, Chris Godsil, Krystal Guo, John Sinkovic

Electronic Journal of Linear Algebra

The rank of the average mixing matrix of trees with all eigenvalues distinct, is investigated. The rank of the average mixing matrix of a tree on n vertices with n distinct eigenvalues is bounded above by ⌈n/2⌉. Computations on trees up to 20 vertices suggest that the rank attains this upper bound most of the time. An infinite family of trees whose average mixing matrices have ranks which are bounded away from this upper bound, is given. A lower bound on the rank of the average mixing matrix of a tree, is also given.


Two Results In Drawing Graphs On Surfaces, Joshua E. Fallon 2018 Louisiana State University and Agricultural and Mechanical College

Two Results In Drawing Graphs On Surfaces, Joshua E. Fallon

LSU Doctoral Dissertations

In this work we present results on crossing-critical graphs drawn on non-planar surfaces and results on edge-hamiltonicity of graphs on the Klein bottle. We first give an infinite family of graphs that are 2-crossing-critical on the projective plane. Using this result, we construct 2-crossing-critical graphs for each non-orientable surface. Next, we use 2-amalgamations to construct 2-crossing-critical graphs for each orientable surface other than the sphere. Finally, we contribute to the pursuit of characterizing 4-connected graphs that embed on the Klein bottle and fail to be edge-hamiltonian. We show that known 4-connected counterexamples to edge-hamiltonicity on the Klein bottle are hamiltonian ...


$\Gamma'$-Realizability And Other Musings On Inverse Domination, John Asplund, Joe Chaffee, James M. Hammer III, Matt Noble 2018 Dalton State College

$\Gamma'$-Realizability And Other Musings On Inverse Domination, John Asplund, Joe Chaffee, James M. Hammer Iii, Matt Noble

Theory and Applications of Graphs

We introduce and study $\gamma'$-realizable sequences. For a finite, simple graph $G$ containing no isolated vertices, $I \subseteq V(G)$ is said to be an \emph{inverse dominating set} if $I$ dominates all of $G$ and $I$ is contained by the complement of some minimum dominating set $D$. Define a sequence of positive integers $(x_1, \ldots , x_n)$ to be \emph{$\gamma'$-realizable} if there exists a graph $G$ having exactly $n$ distinct minimum dominating sets $D_1, \ldots, D_n$ where for each $i \in \{1, \ldots, n\}$, the minimum size of an inverse dominating set in $V(G) \setminus D_i ...


The Search For The Cyclic Sieving Phenomenon In Plane Partitions, William J. Asztalos 2018 DePaul University

The Search For The Cyclic Sieving Phenomenon In Plane Partitions, William J. Asztalos

DePaul Discoveries

The efforts of this research project are best understood in the context of the subfield of dynamical combinatorics, in which one enumerates a set of combinatorial objects by defining some action to guide the search for underlying structures. While there are many examples with varying degrees of complexity, the necklace problem, which concerns the possible unique configurations of beads in a ring up to rotational symmetry, is a well-known example. Though this sort of approach to enumeration has been around for a century or more, activity in this area has intensified in the last couple of decades. Perhaps the most ...


On The Distance And Distance Signless Laplacian Eigenvalues Of Graphs And The Smallest Gersgorin Disc, Fouzul Atik, Pratima Panigrahi 2018 Indian Institute of Technology Kharagpur

On The Distance And Distance Signless Laplacian Eigenvalues Of Graphs And The Smallest Gersgorin Disc, Fouzul Atik, Pratima Panigrahi

Electronic Journal of Linear Algebra

The \emph{distance matrix} of a simple connected graph $G$ is $D(G)=(d_{ij})$, where $d_{ij}$ is the distance between the $i$th and $j$th vertices of $G$. The \emph{distance signless Laplacian matrix} of the graph $G$ is $D_Q(G)=D(G)+Tr(G)$, where $Tr(G)$ is a diagonal matrix whose $i$th diagonal entry is the transmission of the vertex $i$ in $G$. In this paper, first, upper and lower bounds for the spectral radius of a nonnegative matrix are constructed. Applying this result, upper and lower bounds for the distance and distance signless ...


Golden Arm: A Probabilistic Study Of Dice Control In Craps, Donald R. Smith, Robert Scott III 2018 Monmouth University

Golden Arm: A Probabilistic Study Of Dice Control In Craps, Donald R. Smith, Robert Scott Iii

UNLV Gaming Research & Review Journal

This paper calculates how much control a craps shooter must possess on dice outcomes to eliminate the house advantage. A golden arm is someone who has dice control (or a rhythm roller or dice influencer). There are various strategies for dice control in craps. We discuss several possibilities of dice control that would result in several different mathematical models of control. We do not assert whether dice control is possible or not (there is a lack of published evidence). However, after studying casino-legal methods described by dice-control advocates, we can see only one realistic mathematical model that describes the resulting ...


Vector Partitions, Jennifer French 2018 East Tennessee State University

Vector Partitions, Jennifer French

Electronic Theses and Dissertations

Integer partitions have been studied by many mathematicians over hundreds of years. Many identities exist between integer partitions, such as Euler’s discovery that every number has the same amount of partitions into distinct parts as into odd parts. These identities can be proven using methods such as conjugation or generating functions. Over the years, mathematicians have worked to expand partition identities to vectors. In 1963, M. S. Cheema proved that every vector has the same number of partitions into distinct vectors as into vectors with at least one component odd. This parallels Euler’s result for integer partitions. The ...


Exploring Random Walks On Graphs For Protein Function Prediction, Angela M. Dahl 2018 Bowdoin College

Exploring Random Walks On Graphs For Protein Function Prediction, Angela M. Dahl

Honors Projects

No abstract provided.


Secure Multiparty Protocol For Differentially-Private Data Release, Anthony Harris 2018 Boise State University

Secure Multiparty Protocol For Differentially-Private Data Release, Anthony Harris

Boise State University Theses and Dissertations

In the era where big data is the new norm, a higher emphasis has been placed on models which guarantees the release and exchange of data. The need for privacy-preserving data arose as more sophisticated data-mining techniques led to breaches of sensitive information. In this thesis, we present a secure multiparty protocol for the purpose of integrating multiple datasets simultaneously such that the contents of each dataset is not revealed to any of the data owners, and the contents of the integrated data do not compromise individual’s privacy. We utilize privacy by simulation to prove that the protocol is ...


Covering Arrays For Equivalence Classes Of Words, Joshua Cassels, Anant Godbole 2018 East Tennessee State University

Covering Arrays For Equivalence Classes Of Words, Joshua Cassels, Anant Godbole

Undergraduate Honors Theses

Covering arrays for words of length t over a d letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the dt t-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weighted sum are equivalent. In both cases we produce logarithmic upper bounds on ...


On Some Geometry Of Graphs, Zachary S. McGuirk 2018 The Graduate Center, City University of New York

On Some Geometry Of Graphs, Zachary S. Mcguirk

All Dissertations, Theses, and Capstone Projects

In this thesis we study the intrinsic geometry of graphs via the constants that appear in discretized partial differential equations associated to those graphs. By studying the behavior of a discretized version of Bochner's inequality for smooth manifolds at the cone point for a cone over the set of vertices of a graph, a lower bound for the internal energy of the underlying graph is obtained. This gives a new lower bound for the size of the first non-trivial eigenvalue of the graph Laplacian in terms of the curvature constant that appears at the cone point and the size ...


On Coding For Partial Erasure Channels, Carolyn Mayer 2018 University of Nebraska - Lincoln

On Coding For Partial Erasure Channels, Carolyn Mayer

Dissertations, Theses, and Student Research Papers in Mathematics

Error correcting codes have been essential to the technology we use in everyday life in digital storage, wireless communication, barcodes, and much more. Different channel models are used for different types of communication (for example, if information is sent to one person or to many people) and different types of errors. Partial erasure channels were recently introduced to model applications in which some information remains after an erasure event. These remnants of information may be used to increase the chances of successful decoding. We introduce a new partial erasure channel in which partial erasures correspond to individual bit erasures in ...


Graphs With Few Spanning Substructures, Jessica De Silva 2018 University of Nebraska - Lincoln

Graphs With Few Spanning Substructures, Jessica De Silva

Dissertations, Theses, and Student Research Papers in Mathematics

In this thesis, we investigate a number of problems related to spanning substructures of graphs. The first few chapters consider extremal problems related to the number of forest-like structures of a graph. We prove that one can find a threshold graph which contains the minimum number of spanning pseudoforests, as well as rooted spanning forests, amongst all graphs on n vertices and e edges. This has left the open question of exactly which threshold graphs have the minimum number of these spanning substructures. We make progress towards this question in particular cases of spanning pseudoforests.

The final chapter takes on ...


Digital Commons powered by bepress