Discrete Mathematics and Combinatorics Commons™

Articles 1 - 30 of 945

Full-Text Articles in Discrete Mathematics and Combinatorics

Laplacian Spectral Characterization Of Signed Sun Graphs, Fatemeh Motialah, Mohammad Hassan Shirdareh Haghighi Oct 2019

Laplacian Spectral Characterization Of Signed Sun Graphs, Fatemeh Motialah, Mohammad Hassan Shirdareh Haghighi

Theory and Applications of Graphs

A sun $SG_{n}$ is a graph of order $2n$ consisting of a cycle $C_{n}$, $n\geq 3$, to each vertex of it a pendant edge is attached. In this paper, we prove that unbalanced signed sun graphs are determined by their Laplacian spectra. Also we show that a balanced signed sun graph is determined by its Laplacian spectrum if and only if $n$ is odd.

Making Kr+1-Free Graphs R-Partite, József Balogh, Felix Christian Clemen, Mikhail Lavrov, Bernard Lidický, Florian Pfender Oct 2019

Making Kr+1-Free Graphs R-Partite, József Balogh, Felix Christian Clemen, Mikhail Lavrov, Bernard Lidický, Florian Pfender

Bernard Lidický

The Erdős–Simonovits stability theorem states that for all ε > 0 there exists α > 0 such that if G is a Kr+1-free graph on n vertices with e(G) > ex(n, Kr+1) − αn2, then one can remove εn2 edges from G to obtain an r-partite graph. Fu¨redi gave a short proof that one can choose α = ε. We give a bound for the relationship of α and ε which is asymptotically sharp as ε → 0.

Oct 2019

Sdrap: An Annotation Pipeline For Highly Scrambled Genomes, Jasper Braun

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.

Mathematical Models For Describing Molecular Self-Assembly, Margherita Maria Ferrari Oct 2019

Mathematical Models For Describing Molecular Self-Assembly, Margherita Maria Ferrari

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.

Loop Homology Of Bi-Secondary Structures, Andrei Bura Oct 2019

Loop Homology Of Bi-Secondary Structures, Andrei Bura

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.

Design Of Experiments For Unique Wiring Diagram Identification, Elena Dimitrova Oct 2019

Design Of Experiments For Unique Wiring Diagram Identification, Elena Dimitrova

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.

On An Enhancement Of Rna Probing Data Using Information Theory, Thomas J.X. Li, Christian M. Reidys Oct 2019

On An Enhancement Of Rna Probing Data Using Information Theory, Thomas J.X. Li, Christian M. Reidys

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.

Oct 2019

Research For Educators: Modeling Graph Theory For Nontraditional Math Researchers, Erwin Cornelius

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.

Making Kr+1-Free Graphs R-Partite, József Balogh, Felix Christian Clemen, Mikhail Lavrov, Bernard Lidický, Florian Pfender Sep 2019

Making Kr+1-Free Graphs R-Partite, József Balogh, Felix Christian Clemen, Mikhail Lavrov, Bernard Lidický, Florian Pfender

Mathematics Publications

The Erdős–Simonovits stability theorem states that for all ε > 0 there exists α > 0 such that if G is a Kr+1-free graph on n vertices with e(G) > ex(n, Kr+1) − αn2, then one can remove εn2 edges from G to obtain an r-partite graph. Fu¨redi gave a short proof that one can choose α = ε. We give a bound for the relationship of α and ε which is asymptotically sharp as ε → 0.

Sharp Bounds For Decomposing Graphs Into Edges And Triangles, Adam Blumenthal, Bernard Lidicky, Oleg Pikhurko, Yanitsa Pehova, Florian Pfender, Jan Volec Sep 2019

Sharp Bounds For Decomposing Graphs Into Edges And Triangles, Adam Blumenthal, Bernard Lidicky, Oleg Pikhurko, Yanitsa Pehova, Florian Pfender, Jan Volec

Bernard Lidický

Let pi3(G) be the minimum of twice the number of edges plus three times the number of triangles over all edge-decompositions of G into copies of K2 and K3. We are interested in the value of pi3(n), the maximum of pi3(G) over graphs G with n vertices. This specific extremal function was first studied by Gyori and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320], who showed that pi3(n)<9n2/16.
In a recent advance on this problem, Kral, Lidicky, Martins and Pehova [arXiv:1710:08486] proved via flag ...

Fractional Strong Matching Preclusion For Two Variants Of Hypercubes, Huifen Ge, Tianlong Ma, Miaolin Wu, Yuzhi Xiao Sep 2019

Fractional Strong Matching Preclusion For Two Variants Of Hypercubes, Huifen Ge, Tianlong Ma, Miaolin Wu, Yuzhi Xiao

Theory and Applications of Graphs

Let F be a subset of edges and vertices of a graph G. If G-F has no fractional perfect matching, then F is a fractional strong matching preclusion set of G. The fractional strong matching preclusion number is the cardinality of a minimum fractional strong matching preclusion set. In this paper, we mainly study the fractional strong matching preclusion problem for two variants of hypercubes, the multiply twisted cube and the locally twisted cube, which are two of the most popular interconnection networks. In addition, we classify all the optimal fractional strong matching preclusion set of each.

On The Second Least Distance Eigenvalue Of A Graph, Xueyi Huang, Qiongxiang Huang, Lu Lu Sep 2019

On The Second Least Distance Eigenvalue Of A Graph, Xueyi Huang, Qiongxiang Huang, Lu Lu

Lu Lu

Let $G$ be a connected graph on $n$ vertices, and let $D(G)$ be the distance matrix of $G$. Let $\partial_1(G)\ge\partial_2(G)\ge\cdots\ge\partial_n(G)$ denote the eigenvalues of $D(G)$. In this paper, the connected graphs with @n􀀀1(G) at least the smallest root of $x^3=3x^2-11x-6 = 0$ are determined. Additionally, some non-isomorphic distance cospectral graphs are given.

Aug 2019

Colored Complete Hypergraphs Containing No Rainbow Berge Triangles, Colton Magnant

Theory and Applications of Graphs

The study of graph Ramsey numbers within restricted colorings, in particular forbidding a rainbow triangle, has recently been blossoming under the name Gallai-Ramsey numbers. In this work, we extend the main structural tool from rainbow triangle free colorings of complete graphs to rainbow Berge triangle free colorings of hypergraphs. In doing so, some other concepts and results are also translated from graphs to hypergraphs.

Spn Graphs, Leslie Hogben, Naomi Shaked-Monderer Aug 2019

Spn Graphs, Leslie Hogben, Naomi Shaked-Monderer

Electronic Journal of Linear Algebra

A simple graph G is an SPN graph if every copositive matrix having graph G is the sum of a positive semidefinite and nonnegative matrix. SPN graphs were introduced in [N. Shaked-Monderer. SPN graphs: When copositive = SPN. Linear Algebra Appl., 509:82{113, 2016.], where it was conjectured that the complete subdivision graph of K4 is an SPN graph. This conjecture is disproved, which in conjunction with results in the Shaked-Monderer paper show that a subdivision of K_4 is a SPN graph if and only if at most one edge is subdivided. It is conjectured that a graph is an ...

Alpha Adjacency: A Generalization Of Adjacency Matrices, Matt Hudelson, Judi Mcdonald, Enzo Wendler Aug 2019

Alpha Adjacency: A Generalization Of Adjacency Matrices, Matt Hudelson, Judi Mcdonald, Enzo Wendler

Electronic Journal of Linear Algebra

B. Shader and W. So introduced the idea of the skew adjacency matrix. Their idea was to give an orientation to a simple undirected graph G from which a skew adjacency matrix S(G) is created. The -adjacency matrix extends this idea to an arbitrary field F. To study the underlying undirected graph, the average -characteristic polynomial can be created by averaging the characteristic polynomials over all the possible orientations. In particular, a Harary-Sachs theorem for the average-characteristic polynomial is derived and used to determine a few features of the graph from the average-characteristic polynomial.

On Sign Pattern Matrices That Allow Or Require Algebraic Positivity, Diane Christine Pelejo, Jean Leonardo Abagat Aug 2019

On Sign Pattern Matrices That Allow Or Require Algebraic Positivity, Diane Christine Pelejo, Jean Leonardo Abagat

Electronic Journal of Linear Algebra

A square matrix M with real entries is algebraically positive (AP) if there exists a real polynomial p such that all entries of the matrix p(M) are positive. A square sign pattern matrix S allows algebraic positivity if there is an algebraically positive matrix M whose sign pattern is S. On the other hand, S requires algebraic positivity if matrix M, having sign pattern S, is algebraically positive. Motivated by open problems raised in a work of Kirkland, Qiao, and Zhan (2016) on AP matrices, all nonequivalent irreducible 3 by 3 sign pattern matrices are listed and classify into ...

On Orthogonal Matrices With Zero Diagonal, Robert F. Bailey, Robert Craigen Aug 2019

On Orthogonal Matrices With Zero Diagonal, Robert F. Bailey, Robert Craigen

Electronic Journal of Linear Algebra

This paper considers real orthogonal $n\times n$ matrices whose diagonal entries are zero and off-diagonal entries nonzero, which are referred to as $\OMZD(n)$. It is shown that there exists an $\OMZD(n)$ if and only if $n\neq 1,\ 3$, and that a symmetric $\OMZD(n)$ exists if and only if $n$ is even and $n\neq 4$. Also, a construction of $\OMZD(n)$ obtained from doubly regular tournaments is given. Finally, the results are applied to determine the minimum number of distinct eigenvalues of matrices associated with some families of graphs, and the related notion of orthogonal ...

On The Block Structure And Frobenius Normal Form Of Powers Of Matrices, Mashael M. Al Baidani, Judi J. Mcdonald Aug 2019

On The Block Structure And Frobenius Normal Form Of Powers Of Matrices, Mashael M. Al Baidani, Judi J. Mcdonald

Electronic Journal of Linear Algebra

The Frobenius normal form of a matrix is an important tool in analyzing its properties. When a matrix is powered up, the Frobenius normal form of the original matrix and that of its powers need not be the same. In this article, conditions on a matrix $A$ and the power $q$ are provided so that for any invertible matrix $S$, if $S^{-1}A^qS$ is block upper triangular, then so is $S^{-1}AS$ when partitioned conformably. The result is established for general matrices over any field. It is also observed that the contributions of the index of cyclicity ...

Analysis Of Feast Spectral Approximations Using The Dpg Discretization, Jay Gopalakrishnan, Luka Grubišić, Jeffrey S. Ovall, Benjamin Q. Parker Aug 2019

Analysis Of Feast Spectral Approximations Using The Dpg Discretization, Jay Gopalakrishnan, Luka Grubišić, Jeffrey S. Ovall, Benjamin Q. Parker

Jeffrey S. Ovall

A filtered subspace iteration for computing a cluster of eigenvalues and its accompanying eigenspace, known as “FEAST”, has gained considerable attention in recent years. This work studies issues that arise when FEAST is applied to compute part of the spectrum of an unbounded partial differential operator. Specifically, when the resolvent of the partial differential operator is approximated by the discontinuous Petrov Galerkin (DPG) method, it is shown that there is no spectral pollution. The theory also provides bounds on the discretization errors in the spectral approximations. Numerical experiments for simple operators illustrate the theory and also indicate the value of ...

Analysis Of Feast Spectral Approximations Using The Dpg Discretization, Jay Gopalakrishnan, Luka Grubišić, Jeffrey S. Ovall, Benjamin Q. Parker Aug 2019

Analysis Of Feast Spectral Approximations Using The Dpg Discretization, Jay Gopalakrishnan, Luka Grubišić, Jeffrey S. Ovall, Benjamin Q. Parker

Jay Gopalakrishnan

A filtered subspace iteration for computing a cluster of eigenvalues and its accompanying eigenspace, known as “FEAST”, has gained considerable attention in recent years. This work studies issues that arise when FEAST is applied to compute part of the spectrum of an unbounded partial differential operator. Specifically, when the resolvent of the partial differential operator is approximated by the discontinuous Petrov Galerkin (DPG) method, it is shown that there is no spectral pollution. The theory also provides bounds on the discretization errors in the spectral approximations. Numerical experiments for simple operators illustrate the theory and also indicate the value of ...

Classification Of Minimal Separating Sets In Low Genus Surfaces, J. J. P. Veerman, William Maxwell, Victor Rielly, Austin K. Williams Aug 2019

Classification Of Minimal Separating Sets In Low Genus Surfaces, J. J. P. Veerman, William Maxwell, Victor Rielly, Austin K. Williams

J. J. P. Veerman

Consider a surface S and let MS. If S \ M is not connected, then we say M separates S, and we refer to M as a separating set of S. If M separates S, and no proper subset of M separates S, then we say M is a minimal separating set of S. In this paper we use computational methods of combinatorial topology to classify the minimal separating sets of the orientable surfaces of genus g = 2 and g = 3. The classification for genus 0 and 1 was done in earlier work, using methods of algebraic topology.

Aug 2019

Of Matroid Polytopes, Chow Rings And Character Polynomials, Ahmed Ashraf

Electronic Thesis and Dissertation Repository

Matroids are combinatorial structures that capture various notions of independence. Recently there has been great interest in studying various matroid invariants. In this thesis, we study two such invariants: Volume of matroid base polytopes and the Tutte polynomial. We gave an approach to computing volume of matroid base polytopes using cyclic flats and apply it to the case of sparse paving matroids. For the Tutte polynomial, we recover (some of) its coefficients as degrees of certain forms in the Chow ring of underlying matroid. Lastly, we study the stability of characters of the symmetric group via character polynomials. We show ...

Choose Your Own Adventure: An Analysis Of Interactive Gamebooks Using Graph Theory, D'Andre Adams, Daniela Beckelhymer, Alison Marr Jul 2019

Choose Your Own Adventure: An Analysis Of Interactive Gamebooks Using Graph Theory, D'Andre Adams, Daniela Beckelhymer, Alison Marr

Journal of Humanistic Mathematics

"BEWARE and WARNING! This book is different from other books. You and YOU ALONE are in charge of what happens in this story." This is the captivating introduction to every book in the interactive novel series, Choose Your Own Adventure (CYOA). Our project uses the mathematical field of graph theory to analyze forty books from the CYOA book series for ages 9-12. We first began by drawing the digraphs of each book. Then we analyzed these digraphs by collecting structural data such as longest path length (i.e. longest story length) and number of vertices with outdegree zero (i.e ...

Coloring Count Cones Of Planar Graphs, Zdenek Dvorak, Bernard Lidicky Jul 2019

Coloring Count Cones Of Planar Graphs, Zdenek Dvorak, Bernard Lidicky

Bernard Lidický

For a plane near-triangulation G with the outer face bounded by a cycle C, let n⋆G denote the function that to each 4-coloring ψ of C assigns the number of ways ψ extends to a 4-coloring of G. The block-count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function n⋆G belongs to a certain cone in the space of all functions from 4-colorings of C to real numbers. We investigate the properties of this cone for |C|=5, formulate a conjecture strengthening the ...

Coloring Count Cones Of Planar Graphs, Zdenek Dvorak, Bernard Lidicky Jul 2019

Coloring Count Cones Of Planar Graphs, Zdenek Dvorak, Bernard Lidicky

Mathematics Publications

For a plane near-triangulation G with the outer face bounded by a cycle C, let n⋆G denote the function that to each 4-coloring ψ of C assigns the number of ways ψ extends to a 4-coloring of G. The block-count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function n⋆G belongs to a certain cone in the space of all functions from 4-colorings of C to real numbers. We investigate the properties of this cone for |C|=5, formulate a conjecture strengthening the ...

Non-Sparse Companion Matrices, Louis Deaett, Jonathan Fischer, Colin Garnett, Kevin N. Vander Meulen Jul 2019

Non-Sparse Companion Matrices, Louis Deaett, Jonathan Fischer, Colin Garnett, Kevin N. Vander Meulen

Electronic Journal of Linear Algebra

Given a polynomial $p(z)$, a companion matrix can be thought of as a simple template for placing the coefficients of $p(z)$ in a matrix such that the characteristic polynomial is $p(z)$. The Frobenius companion and the more recently-discovered Fiedler companion matrices are examples. Both the Frobenius and Fiedler companion matrices have the maximum possible number of zero entries, and in that sense are sparse. In this paper, companion matrices are explored that are not sparse. Some constructions of non-sparse companion matrices are provided, and properties that all companion matrices must exhibit are given. For example, it is ...

Properties Of Functionally Alexandroff Topologies And Their Lattice, Jacob Scott Menix Jul 2019

Properties Of Functionally Alexandroff Topologies And Their Lattice, Jacob Scott Menix

Masters Theses & Specialist Projects

This thesis explores functionally Alexandroff topologies and the order theory asso- ciated when considering the collection of such topologies on some set X. We present several theorems about the properties of these topologies as well as their partially ordered set.

The first chapter introduces functionally Alexandroff topologies and motivates why this work is of interest to topologists. This chapter explains the historical context of this relatively new type of topology and how this work relates to previous work in topology. Chapter 2 presents several theorems describing properties of functionally Alexandroff topologies ad presents a characterization for the functionally Alexandroff topologies ...

List-Distinguishing Cartesian Products Of Cliques, Michael Ferrara, Zoltan Füredi, Sogol Jahanbekam, Paul Wenger Jun 2019

List-Distinguishing Cartesian Products Of Cliques, Michael Ferrara, Zoltan Füredi, Sogol Jahanbekam, Paul Wenger

Sogol Jahanbekam

The distinguishing number of a graph G, denoted D(G), is the minimum number of colors needed to produce a coloring of the vertices of G so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment L on a graph G is a function that assigns each vertex of G a set of colors. An L-coloring of G is a coloring in which each vertex is colored with a color from L(v). The list distinguishing number of G, denoted Dℓ(G) is the minimum k such that every list assignment L that assigns a list ...

The Mystery Of Frobenius Symmetry, Maciej Piwowarczyk Jun 2019

The Mystery Of Frobenius Symmetry, Maciej Piwowarczyk

DePaul Discoveries

In this project we studied the mathematical concept of the Frobenius number and some curious patterns that come with it. One common example of the Frobenius number is the Coin Problem: If handed two denominations of coins, say 4¢ and 5¢, and asked to create all possible values, we will eventually find ourselves in a position where we can make any value. With 4¢ and 5¢ coins, we can create any value above 11¢, but not 11¢ itself. So, that makes 11 the Frobenius number of 4 and 5. What we explore in this paper is a pattern we call ...

Analogues Between Leibniz's Harmonic Triangle And Pascal's Arithmetic Triangle, Lacey Taylor James Jun 2019

Analogues Between Leibniz's Harmonic Triangle And Pascal's Arithmetic Triangle, Lacey Taylor James

Electronic Theses, Projects, and Dissertations

This paper will discuss the analogues between Leibniz's Harmonic Triangle and Pascal's Arithmetic Triangle by utilizing mathematical proving techniques like partial sums, committees, telescoping, mathematical induction and applying George Polya's perspective. The topics presented in this paper will show that Pascal's triangle and Leibniz's triangle both have hockey stick type patterns, patterns of sums within shapes, and have the natural numbers, triangular numbers, tetrahedral numbers, and pentatope numbers hidden within. In addition, this paper will show how Pascal's Arithmetic Triangle can be used to construct Leibniz's Harmonic Triangle and show how both triangles ...