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

Discrete Mathematics and Combinatorics Commons

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

523 Full-Text Articles 616 Authors 52363 Downloads 66 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

523 full-text articles. Page 1 of 16.

Tree Diagrams For String Links, Blake Mellor 2017 Loyola Marymount University

Tree Diagrams For String Links, Blake Mellor

Blake Mellor

In previous work, the author defined the intersection graph of a chord diagram associated with string links (as in the theory of finite type invariants). In this paper, we classify the trees which can be obtained as intersection graphs of string link diagrams.


Tree Diagrams For String Links Ii: Determining Chord Diagrams, Blake Mellor 2017 Loyola Marymount University

Tree Diagrams For String Links Ii: Determining Chord Diagrams, Blake Mellor

Blake Mellor

In previous work, we defined the intersection graph of a chord diagram associated with a string link (as in the theory of finite type invariants). In this paper, we look at the case when this graph is a tree, and we show that in many cases these trees determine the chord diagram (modulo the usual 1-term and 4-term relations).


Symmetries Of Embedded Complete Bipartite Graphs, Erica Flapan, Nicole Lehle, Blake Mellor, Matt Pittluck, Xan Vongsathorn 2017 Loyola Marymount University

Symmetries Of Embedded Complete Bipartite Graphs, Erica Flapan, Nicole Lehle, Blake Mellor, Matt Pittluck, Xan Vongsathorn

Blake Mellor

We characterize which automorphisms of an arbitrary complete bipartite graph Kn,m can be induced by a homeomorphism of some embedding of the graph in S3.


Chord Diagrams And Gauss Codes For Graphs, Thomas Fleming, Blake Mellor 2017 Loyola Marymount University

Chord Diagrams And Gauss Codes For Graphs, Thomas Fleming, Blake Mellor

Blake Mellor

Chord diagrams on circles and their intersection graphs (also known as circle graphs) have been intensively studied, and have many applications to the study of knots and knot invariants, among others. However, chord diagrams on more general graphs have not been studied, and are potentially equally valuable in the study of spatial graphs. We will define chord diagrams for planar embeddings of planar graphs and their intersection graphs, and prove some basic results. Then, as an application, we will introduce Gauss codes for immersions of graphs in the plane and give algorithms to determine whether a particular crossing sequence is ...


Edge Colorings Of K(M,N) With M+N-1 Colors Which Forbid Rainbow Cycles, Peter Johnson, Claire Zhang 2017 Auburn University Main Campus

Edge Colorings Of K(M,N) With M+N-1 Colors Which Forbid Rainbow Cycles, Peter Johnson, Claire Zhang

Theory and Applications of Graphs

For positive integers m, n, the greatest number of colors that can appear in an edge coloring of K(m,n) which avoids rainbow cycles is m + n - 1. Here these colorings are constructively characterized. It turns out that these colorings can be encoded by certain vertex labelings of full binary trees with m + n leafs.


Investigations Into Difference Equations By De Moivre And D. Bernoulli, Dave Ruch 2017 Ursinus College

Investigations Into Difference Equations By De Moivre And D. Bernoulli, Dave Ruch

Discrete Mathematics

No abstract provided.


Polynomial Reconstruction Of Signed Graphs Whose Least Eigenvalue Is Close To -2, Slobodan K. Simić, Zoran Stanic 2016 University of Belgrade

Polynomial Reconstruction Of Signed Graphs Whose Least Eigenvalue Is Close To -2, Slobodan K. Simić, Zoran Stanic

Electronic Journal of Linear Algebra

The polynomial reconstruction problem for simple graphs has been considered in the literature for more than forty years and is not yet resolved except for some special classes of graphs. Recently, the same problem has been put forward for signed graphs. Here, the reconstruction of the characteristic polynomial of signed graphs whose vertex-deleted subgraphs have least eigenvalue greater than $-2$ is considered.


Planar Graphs, Biplanar Graphs And Graph Thickness, Sean M. Hearon 2016 California State University - San Bernardino

Planar Graphs, Biplanar Graphs And Graph Thickness, Sean M. Hearon

Electronic Theses, Projects, and Dissertations

A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.


Potentially Nilpotent Tridiagonal Sign Patterns Of Order 4, Yubin Gao, Yanling Shao 2016 North University of China

Potentially Nilpotent Tridiagonal Sign Patterns Of Order 4, Yubin Gao, Yanling Shao

Electronic Journal of Linear Algebra

An $n\times n$ sign pattern ${\cal A}$ is said to be potentially nilpotent (PN) if there exists some nilpotent real matrix $B$ with sign pattern ${\cal A}$. In [M.~Arav, F.~Hall, Z.~Li, K.~Kaphle, and N.~Manzagol.Spectrally arbitrary tree sign patterns of order $4$, {\em Electronic Journal of Linear Algebra}, 20:180--197, 2010.], the authors gave some open questions, and one of them is the following: {\em For the class of $4 \times 4$ tridiagonal sign patterns, is PN (together with positive and negative diagonal entries) equivalent to being SAP?}\ In this paper, a positive answer ...


Bounds On The Expected Size Of The Maximum Agreement Subtree, Colby Long, Daniel Irving Bernstein, Lam Si Tung Ho, Mike Steel, Katherine St. John, Seth Sullivant 2016 The Ohio State University

Bounds On The Expected Size Of The Maximum Agreement Subtree, Colby Long, Daniel Irving Bernstein, Lam Si Tung Ho, Mike Steel, Katherine St. John, Seth Sullivant

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


Exploring The Space Of Rna Secondary Structures, Heather C. Smith 2016 Georgia Institute of Technology

Exploring The Space Of Rna Secondary Structures, Heather C. Smith

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


Markov Chains On Graphical Models Of Gene Regulation, Megan Bernstein 2016 Georgia Institute of Technology

Markov Chains On Graphical Models Of Gene Regulation, Megan Bernstein

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


Genome Rearrangement: Graphs And Matrices, Jeffrey Davis 2016 Emory University

Genome Rearrangement: Graphs And Matrices, Jeffrey Davis

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


On The Expected Number Of Crossings In A Tanglegram, Eva Czabarka 2016 University of South Carolina

On The Expected Number Of Crossings In A Tanglegram, Eva Czabarka

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


On The Perfect Reconstruction Of The Structure Of Dynamic Networks, Alan Veliz-Cuba 2016 University of Dayton

On The Perfect Reconstruction Of The Structure Of Dynamic Networks, Alan Veliz-Cuba

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


Spectral Graph Theory And New Stability Measures For Deterministic Gene Regulatory Networks, Fusun Akman, Devin Akman 2016 Illinois State University

Spectral Graph Theory And New Stability Measures For Deterministic Gene Regulatory Networks, Fusun Akman, Devin Akman

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


Rogers-Ramanujan Computer Searches, James McLaughlin, Andrew Sills, Peter Zimmer 2016 West Chester University of Pennsylvania

Rogers-Ramanujan Computer Searches, James Mclaughlin, Andrew Sills, Peter Zimmer

James McLaughlin

We describe three computer searches (in PARI/GP, Maple, and Mathematica, respectively) which led to the discovery of a number of identities of Rogers–Ramanujan type and identities of false theta functions.


Preservers Of Term Ranks And Star Cover Numbers Of Symmetric Matrices, LeRoy B. Beasley 2016 Utah State University

Preservers Of Term Ranks And Star Cover Numbers Of Symmetric Matrices, Leroy B. Beasley

Electronic Journal of Linear Algebra

Let $\S$ denote the set of symmetric matrices over some semiring, $\s$. A line of $A\in\S$ is a row or a column of $A$. A star of $A$ is the submatrix of $A$ consisting of a row and the corresponding column of $A$. The term rank of $A$ is the minimum number of lines that contain all the nonzero entries of $A$. The star cover number is the minimum number of stars that contain all the nonzero entries of $A$. This paper investigates linear operators that preserve sets of symmetric matrices of specified term rank and sets of ...


Cycle Structures Of Orthomorphisms Extending Partial Orthomorphisms Of Boolean Groups, Nichole Louise Schimanski, John S. Caughman IV 2016 Portland State University

Cycle Structures Of Orthomorphisms Extending Partial Orthomorphisms Of Boolean Groups, Nichole Louise Schimanski, John S. Caughman Iv

Mathematics and Statistics Faculty Publications and Presentations

A partial orthomorphism of a group GG (with additive notation) is an injection π:S→G for some S⊆G such that π(x)−x ≠ π(y) for all distinct x,y∈S. We refer to |S| as the size of π, and if S=G, then π is an orthomorphism. Despite receiving a fair amount of attention in the research literature, many basic questions remain concerning the number of orthomorphisms of a given group, and what cycle types these permutations have.

It is known that conjugation by automorphisms of G forms a group action on the set of orthomorphisms ...


Induced Subgraph Saturated Graphs, Craig M. Tennenhouse 2016 University of New England

Induced Subgraph Saturated Graphs, Craig M. Tennenhouse

Theory and Applications of Graphs

A graph $G$ is said to be \emph{$H$-saturated} if $G$ contains no subgraph isomorphic to $H$ but the addition of any edge between non-adjacent vertices in $G$ creates one. While induced subgraphs are often studied in the extremal case with regard to the removal of edges, we extend saturation to induced subgraphs. We say that $G$ is \emph{induced $H$-saturated} if $G$ contains no induced subgraph isomorphic to $H$ and the addition of any edge to $G$ results in an induced copy of $H$. We demonstrate constructively that there are non-trivial examples of saturated graphs for all ...


Digital Commons powered by bepress