# Discrete Mathematics and Combinatorics Commons™

## All Articles in Discrete Mathematics and Combinatorics

569 full-text articles. Page 1 of 18.

Minimum Rank Of Skew-Symmetric Matrices Described By A Graph, 2017 University of Wyoming

#### Minimum Rank Of Skew-Symmetric Matrices Described By A Graph, Mary Allison, Elizabeth Bodine, Luz Maria Dealba, Joyati Debnath, Laura Deloss, Colin Garnett, Jason Grout, Leslie Hogben, Bokhee Im, Hana Kim, Reshmi Nair, Olga Pryporova, Kendrick Savage, Bryan Shader, Amy Wangsness Wehe

##### Leslie Hogben

The minimum (symmetric) rank of a simple graph G over a field F is the smallest possible rank among all symmetric matrices over F whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. The problem of determining minimum (symmetric) rank has been studied extensively. We define the minimum skew rank of a simple graph G to be the smallest possible rank among all skew-symmetric matrices over F whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We apply ...

The Enhanced Principal Rank Characteristic Sequence For Hermitian Matrices, 2017 Iowa State University

#### The Enhanced Principal Rank Characteristic Sequence For Hermitian Matrices, Steve Butler, M. Catral, H. Tracy Hall, Leslie Hogben, Xavier Martinez-Rivera, Bryan L. Shader, Pauline Van Den Driessche

##### Electronic Journal of Linear Algebra

The enhanced principal rank characteristic sequence (epr-sequence) of an $n\x n$ matrix is a sequence $\ell_1 \ell_2 \cdots \ell_n$, where each $\ell_k$ is ${\tt A}$, ${\tt S}$, or ${\tt N}$ according as all, some, or none of its principal minors of order $k$ are nonzero. There has been substantial work on epr-sequences of symmetric matrices (especially real symmetric matrices) and real skew-symmetric matrices, and incidental remarks have been made about results extending (or not extending) to (complex) Hermitian matrices. A systematic study of epr-sequences of Hermitian matrices is undertaken; the differences with the case of symmetric matrices are quite ...

On The Graceful Cartesian Product Of Alpha-Trees, 2017 Clayton State University

#### On The Graceful Cartesian Product Of Alpha-Trees, Christian Barrientos, Sarah Minion

##### Theory and Applications of Graphs

A \emph{graceful labeling} of a graph $G$ of size $n$ is an injective assignment of integers from the set $\{0,1,\dots,n\}$ to the vertices of $G$ such that when each edge has assigned a \emph{weight}, given by the absolute value of the difference of the labels of its end vertices, all the weights are distinct. A graceful labeling is called an $\alpha$-labeling when the graph $G$ is bipartite, with stable sets $A$ and $B$, and the labels assigned to the vertices in $A$ are smaller than the labels assigned to the vertices in $B$. In ...

Tree Diagrams For String Links, 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.

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, 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, 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, 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.

An Eternal Domination Problem In Grids, 2017 University of North Florida

#### An Eternal Domination Problem In Grids, William Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello

##### Theory and Applications of Graphs

A dynamic domination problem in graphs is considered in which an infinite sequence of attacks occur at vertices with mobile guards; the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack, the vertices containing guards must form a dominating set of the graph. The minimum number of guards that can defend the graph against such an arbitrary sequence of attacks is called the m-eviction number of the graph. In this paper, the m-eviction ...

Zero Forcing Propagation Time On Oriented Graphs, 2017 Saint Olaf College

#### Zero Forcing Propagation Time On Oriented Graphs, Adam Berliner, Chassidy Bozeman, Steve Butler, Minerva Catral, Leslie Hogben, Brenda Kroschel, Jephian C.H. Lin, Nathan Warnberg, Michael Young

##### Mathematics Publications

Zero forcing is an iterative coloring procedure on a graph that starts by initially coloring vertices white and blue and then repeatedly applies the following rule: if any blue vertex has a unique (out-)neighbor that is colored white, then that neighbor is forced to change color from white to blue. An initial set of blue vertices that can force the entire graph to blue is called a zero forcing set. In this paper we consider the minimum number of iterations needed for this color change rule to color all of the vertices blue, also known as the propagation time ...

2017 Ursinus College

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

##### Discrete Mathematics

No abstract provided.

Positive Solutions Of A Singular Fractional Boundary Value Problem With A Fractional Boundary Condition, 2017 Eastern Kentucky University

#### Positive Solutions Of A Singular Fractional Boundary Value Problem With A Fractional Boundary Condition, Jeffrey W. Lyons, Jeffrey T. Neugebauer

##### EKU Faculty and Staff Scholarship

For α (1,2], the singular fractional boundary value problem

D0α+x + f t,x,D0µ+x = 0, 0 < t < 1,

satisfying the boundary conditionsα β µ x(0) = D0β+x(1) = 0, where β (0,α−1], µ (0,α−1], and D0+, D0+ and D0+ are Riemann-Liouville derivatives of order α, β and µ respectively, is considered. Here f satisfies a local Carathéodory condition, and f(t,x,y) may be singular at the value 0 in its space variable x. Using regularization and sequential techniques and Krasnosel’skii ...

Polynomial Reconstruction Of Signed Graphs Whose Least Eigenvalue Is Close To -2, 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, 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.

Latin Squares And Their Applications To Cryptography, 2016 Boise State University

#### Latin Squares And Their Applications To Cryptography, Nathan O. Schmidt

##### Boise State University Theses and Dissertations

A latin square of order-n is an n x n array over a set of n symbols such that every symbol appears exactly once in each row and exactly once in each column. Latin squares encode features of algebraic structures. When an algebraic structure passes certain "latin square tests", it is a candidate for use in the construction of cryptographic systems. A transversal of a latin square is a list of n distinct symbols, one from each row and each column. The question regarding the existence of transversals in latin squares that encode the Cayley tables of finite groups ...

Potentially Nilpotent Tridiagonal Sign Patterns Of Order 4, 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, 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, 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, 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, 2016 Emory University

#### Genome Rearrangement: Graphs And Matrices, Jeffrey Davis

##### Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.