Discrete Mathematics and Combinatorics Commons™

All Articles in Discrete Mathematics and Combinatorics

947 full-text articles. Page 1 of 35.

2019 Georgia Southern University

Forcibly-Biconnected Graphical Degree Sequences: Decision Algorithms And Enumerative Results, Kai Wang

Theory and Applications of Graphs

We present an algorithm to test whether a given graphical degree sequence is forcibly biconnected. The worst case time complexity of the algorithm is shown to be exponential but it is still much better than the previous basic algorithm for this problem. We show through experimental evaluations that the algorithm is efficient on average. We also adapt the classic algorithm of Ruskey et al. and that of Barnes and Savage to obtain some enumerative results about forcibly biconnected graphical degree sequences of given length $n$ and forcibly biconnected graphical partitions of given even integer $n$. Based on these enumerative results ...

Laplacian Spectral Characterization Of Signed Sun Graphs, 2019 Shiraz University

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, 2019 University of Illinois at Urbana-Champaign

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.

2019 Illinois State University

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, 2019 University of South Florida

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, 2019 Illinois State University

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, 2019 California Polytechnic State University, San Luis Obispo

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, 2019 University of Virginia

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.

2019 Illinois State University

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, 2019 University of Illinois at Urbana-Champaign

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, 2019 Iowa State University

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, 2019 School of Computer, Qinghai Normal University

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, 2019 College of Mathematics and Systems Science, Xinjiang University, Urumqi, Xinjiang 830046, P.R.China.

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.

2019 Georgia Southern University

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, 2019 Iowa State University

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

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, 2019 University of the Philippines Diliman

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, 2019 Grenfell Campus, Memorial University of Newfoundland

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, 2019 Washington State University

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, 2019 Portland State University

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