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

Discrete Mathematics and Combinatorics Commons

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

962 Full-Text Articles 1,124 Authors 104,022 Downloads 95 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

962 full-text articles. Page 7 of 36.

Policy-Preferred Paths In As-Level Internet Topology Graphs, Mehmet Engin Tozal 2018 University of Louisiana at Lafayette

Policy-Preferred Paths In As-Level Internet Topology Graphs, Mehmet Engin Tozal

Theory and Applications of Graphs

Using Autonomous System (AS) level Internet topology maps to determine accurate AS-level paths is essential for network diagnostics, performance optimization, security enforcement, business policy management and topology-aware application development. One significant drawback that we have observed in many studies is simplifying the AS-level topology map of the Internet to an undirected graph, and then using the hop distance as a means to find the shortest paths between the ASes. A less significant drawback is restricting the shortest paths to only valley-free paths. Both approaches usually inflate the number of paths between ASes; introduce erroneous paths that do not conform to ...


Design And Analysis Of Graph-Based Codes Using Algebraic Lifts And Decoding Networks, Allison Beemer 2018 University of Nebraska - Lincoln

Design And Analysis Of Graph-Based Codes Using Algebraic Lifts And Decoding Networks, Allison Beemer

Dissertations, Theses, and Student Research Papers in Mathematics

Error-correcting codes seek to address the problem of transmitting information efficiently and reliably across noisy channels. Among the most competitive codes developed in the last 70 years are low-density parity-check (LDPC) codes, a class of codes whose structure may be represented by sparse bipartite graphs. In addition to having the potential to be capacity-approaching, LDPC codes offer the significant practical advantage of low-complexity graph-based decoding algorithms. Graphical substructures called trapping sets, absorbing sets, and stopping sets characterize failure of these algorithms at high signal-to-noise ratios. This dissertation focuses on code design for and analysis of iterative graph-based message-passing decoders. The ...


Minimizing The Number Of 5-Cycles In Graphs With Given Edge-Density, Patrick Bennett, Andrzej Dudek, Bernard Lidicky 2018 Western Michigan University

Minimizing The Number Of 5-Cycles In Graphs With Given Edge-Density, Patrick Bennett, Andrzej Dudek, Bernard Lidicky

Mathematics Publications

Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of cycles C5. We show that every graph of order n and size (1−1k)(n2), where k≥3 is an integer, contains at least (110−12k+1k2−1k3+25k4)n5+o(n5)

copies of C5. This bound is optimal, since a matching upper bound is given by the balanced complete k-partite graph. The proof is based on the flag algebras framework. We also provide a stability result for 2≤k≤73.


Weak Dynamic Coloring Of Planar Graphs, Caroline Accurso, Vitaliy Chernyshov, Leaha Hand, Sogol Jahanbekam, Paul Wenger 2018 DeSales University

Weak Dynamic Coloring Of Planar Graphs, Caroline Accurso, Vitaliy Chernyshov, Leaha Hand, Sogol Jahanbekam, Paul Wenger

Faculty Publications

The k-weak-dynamic number of a graph G is the smallest number of colors we need to color the vertices of G in such a way that each vertex v of degree d(v) sees at least min{k, d(v)} colors on its neighborhood. We use reducible configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.


Zero Forcing Sets And The Minimum Rank Of Graphs, Francesco Barioli, Wayne Barrett, Steve Butler, Sebastian M. Cioabă, Dragoš Cvetković, Shaun M. Fallat, Chris Godsil, Willem Haemers, Leslie Hogben, Rana Mikkelson, Sivaram Narayan, Olga Pryporova, Irene Sciriha, Wasin So, Dragan Stevanović, Hein van der Holst, Kevin Vander Meulen, Amy Wangsness Wehe 2018 University of Tennessee at Chattanooga

Zero Forcing Sets And The Minimum Rank Of Graphs, Francesco Barioli, Wayne Barrett, Steve Butler, Sebastian M. Cioabă, Dragoš Cvetković, Shaun M. Fallat, Chris Godsil, Willem Haemers, Leslie Hogben, Rana Mikkelson, Sivaram Narayan, Olga Pryporova, Irene Sciriha, Wasin So, Dragan Stevanović, Hein Van Der Holst, Kevin Vander Meulen, Amy Wangsness Wehe

Leslie Hogben

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. This paper introduces a new graph parameter, Z(G), that is the minimum size of a zero forcing set of vertices and uses it to bound the minimum rank for numerous families of graphs, often enabling computation of the minimum rank.


The Inverse Eigenvalue Problem Of A Graph, Wayne Barrett, Steve Butler, Shaun Fallat, H. Tracy Hall, Leslie Hogben, Jephian C. H. Lin, Bryan Shader, Michael Young 2018 Brigham Young University

The Inverse Eigenvalue Problem Of A Graph, Wayne Barrett, Steve Butler, Shaun Fallat, H. Tracy Hall, Leslie Hogben, Jephian C. H. Lin, Bryan Shader, Michael Young

Leslie Hogben

No abstract provided.


Eventually Nonnegative Matrices And Their Sign Patterns, Minerva Catral, Craig Erickson, Leslie Hogben, D. D. Olesky, P. van den Driessche 2018 Xavier University

Eventually Nonnegative Matrices And Their Sign Patterns, Minerva Catral, Craig Erickson, Leslie Hogben, D. D. Olesky, P. Van Den Driessche

Leslie Hogben

No abstract provided.


Families Of Graphs With Maximum Nullity Equal To Zero Forcing Number, Joseph S. Alameda, Emelie Curl, Armando Grez, Leslie Hogben, O'Neill Kingston, Alex Schulte, Derek Young, Michael Young 2018 Iowa State University

Families Of Graphs With Maximum Nullity Equal To Zero Forcing Number, Joseph S. Alameda, Emelie Curl, Armando Grez, Leslie Hogben, O'Neill Kingston, Alex Schulte, Derek Young, Michael Young

Mathematics Publications

The maximum nullity of a simple graph G, denoted M(G), is the largest possible nullity over all symmetric real matrices whose ijth entry is nonzero exactly when fi, jg is an edge in G for i =6 j, and the iith entry is any real number. The zero forcing number of a simple graph G, denoted Z(G), is the minimum number of blue vertices needed to force all vertices of the graph blue by applying the color change rule. This research is motivated by the longstanding question of characterizing graphs G for which M(G) = Z(G). The ...


An Update On A Few Permanent Conjectures, Fuzhen Zhang 2018 Nova Southeastern University

An Update On A Few Permanent Conjectures, Fuzhen Zhang

Fuzhen Zhang

We review and update on a few conjectures concerning matrix permanent that are easily stated, understood, and accessible to general math audience. They are: Soules permanent-on-top conjecture†, Lieb permanent dominance conjecture, Bapat and Sunder conjecture† on Hadamard product and diagonal entries, Chollet conjecture on Hadamard product, Marcus conjecture on permanent of permanents, and several other conjectures. Some of these conjectures are recently settled; some are still open.We also raise a few new questions for future study. (†conjectures have been recently settled negatively.)


Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg 2018 Loyola University Chicago

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg

Ronald Greenberg

Magic tricks based on computer science concepts help grab student attention and can motivate them to delve more deeply. Error detection ideas long used by computer scientists provide a rich basis for working magic; probably the most well known trick of this type is one included in the CS Unplugged activities. This paper shows that much more powerful variations of the trick can be performed, some in an unplugged environment and some with computer assistance. Some of the tricks also show off additional concepts in computer science and discrete mathematics.


An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg 2018 Loyola University Chicago

An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg

Ronald Greenberg

I have investigated a problem which may be phrased in many ways, such as finding the probability of answering a given number of questions correctly on a randomly-completed matching test which may have a number of extra "dud" answers. I have determined such probabilities, the average number of correct answers, and other allied results. I have also investigated a related problem involving the number of ways of choosing a different element from each of a certain collection of sets.


On The Inverse Of A Class Of Weighted Graphs, Swarup Kumar Panda, Sukanta Pati 2018 Indian Statistical Institute - Delhi Center

On The Inverse Of A Class Of Weighted Graphs, Swarup Kumar Panda, Sukanta Pati

Electronic Journal of Linear Algebra

In this article, only connected bipartite graphs $G$ with a unique perfect matching $\c{M}$ are considered. Let $G_\w$ denote the weighted graph obtained from $G$ by giving weights to its edges using the positive weight function $\w:E(G)\ar (0,\ity)$ such that $\w(e)=1$ for each $e\in\c{M}$. An unweighted graph $G$ may be viewed as a weighted graph with the weight function $\w\equiv\1$ (all ones vector). A weighted graph $G_\w$ is nonsingular if its adjacency matrix $A(G_\w)$ is nonsingular. The {\em inverse} of a nonsingular weighted graph ...


On The Second Least Distance Eigenvalue Of A Graph, Xueyi Huang, Qiongxiang Huang, Lu Lu 2018 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

Electronic Journal of Linear Algebra

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.


Traveling In Networks With Blinking Nodes, Braxton Carrigan, James Hammer 2018 Southern CT State University

Traveling In Networks With Blinking Nodes, Braxton Carrigan, James Hammer

Theory and Applications of Graphs

We say that a blinking node system modulo $n$ is an ordered pair $(G,L)$ where $G$ is a graph and $L$ is an on-labelling which indicates when vertices can be visited. An On-Hamiltonian walk is a sequence of all the vertices of $G$ such that the position of each vertex modulo $n$ is an integer of the label of that vertex. This paper will primarily investigate finding the shortest On-Hamiltonian walks in a blinking node system on complete graphs and complete bipartite graphs but also establishes the terminology and initial observations for working with blinking node systems on other ...


The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler 2018 Louisiana State University and Agricultural and Mechanical College

The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler

LSU Doctoral Dissertations

This thesis is motivated by a graph-theoretical result of Maffray, which states that a 2-connected graph with no odd cycles exceeding length 3 is bipartite, is isomorphic to K_4, or is a collection of triangles glued together along a common edge. We first prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is M(K_4) or F_7, or M is the cycle matroid of a graph consisting of a collection of triangles glued together along a common edge. This result implies that a 2-connected loopless graph ...


On The Density Of The Odd Values Of The Partition Function, Samuel Judge 2018 Michigan Technological University

On The Density Of The Odd Values Of The Partition Function, Samuel Judge

Dissertations, Master's Theses and Master's Reports

The purpose of this dissertation is to introduce a new approach to the study of one of the most basic and seemingly intractable problems in partition theory, namely the conjecture that the partition function $p(n)$ is equidistributed modulo $2$. We provide a doubly-indexed, infinite family of conjectural identities in the ring of series $\Z_2[[q]]$, which relate $p(n)$ with suitable $t$-multipartition functions, and show how to, in principle, prove each such identity. We will exhibit explicit proofs for $32$ of our identities. However, the conjecture remains open in full generality. A striking consequence of these conjectural identities ...


Distributive Lattice Models Of The Type C One-Rowed Weyl Group Symmetric Functions, William Atkins 2018 Murray State University

Distributive Lattice Models Of The Type C One-Rowed Weyl Group Symmetric Functions, William Atkins

Murray State Theses and Dissertations

We present two families of diamond-colored distributive lattices – one known and one new – that we can show are models of the type C one-rowed Weyl symmetric functions. These lattices are constructed using certain sequences of positive integers that are visualized as filling the boxes of one-rowed partition diagrams. We show how natural orderings of these one-rowed tableaux produce our distributive lattices as sublattices of a more general object, and how a natural coloring of the edges of the associated order diagrams yields a certain diamond-coloring property. We show that each edge-colored lattice possesses a certain structure that is associated with ...


On The Domination Chain Of M By N Chess Graphs, Kathleen Johnson 2018 Murray State University

On The Domination Chain Of M By N Chess Graphs, Kathleen Johnson

Murray State Theses and Dissertations

A survey of the six domination chain parameters for both square and rectangular chess boards are discussed.


A Combinatorial Miscellany: Antipodes, Parking Cars, And Descent Set Powers, Alexander Thomas Happ 2018 University of Kentucky

A Combinatorial Miscellany: Antipodes, Parking Cars, And Descent Set Powers, Alexander Thomas Happ

Theses and Dissertations--Mathematics

In this dissertation we first introduce an extension of the notion of parking functions to cars of different sizes. We prove a product formula for the number of such sequences and provide a refinement using a multi-parameter extension of the Abel--Rothe polynomial. Next, we study the incidence Hopf algebra on the noncrossing partition lattice. We demonstrate a bijection between the terms in the canceled chain decomposition of its antipode and noncrossing hypertrees. Thirdly, we analyze the sum of the 𝑟th powers of the descent set statistic on permutations and how many small prime factors occur in these numbers. These results ...


A General Lower Bound On Gallai-Ramsey Numbers For Non-Bipartite Graphs, Colton Magnant 2018 Georgia Southern University

A General Lower Bound On Gallai-Ramsey Numbers For Non-Bipartite Graphs, Colton Magnant

Theory and Applications of Graphs

Given a graph $H$ and a positive integer $k$, the $k$-color Gallai-Ramsey number $gr_{k}(K_{3} : H)$ is defined to be the minimum number of vertices $n$ for which any $k$-coloring of the complete graph $K_{n}$ contains either a rainbow triangle or a monochromatic copy of $H$. The behavior of these numbers is rather well understood when $H$ is bipartite but when $H$ is not bipartite, this behavior is a bit more complicated. In this short note, we improve upon existing lower bounds for non-bipartite graphs $H$ to a value that we conjecture to be sharp ...


Digital Commons powered by bepress