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

Discrete Mathematics and Combinatorics Commons

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

961 Full-Text Articles 1,123 Authors 104,022 Downloads 95 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

961 full-text articles. Page 6 of 36.

On Some Geometry Of Graphs, Zachary S. McGuirk 2018 The Graduate Center, City University of New York

On Some Geometry Of Graphs, Zachary S. Mcguirk

All Dissertations, Theses, and Capstone Projects

In this thesis we study the intrinsic geometry of graphs via the constants that appear in discretized partial differential equations associated to those graphs. By studying the behavior of a discretized version of Bochner's inequality for smooth manifolds at the cone point for a cone over the set of vertices of a graph, a lower bound for the internal energy of the underlying graph is obtained. This gives a new lower bound for the size of the first non-trivial eigenvalue of the graph Laplacian in terms of the curvature constant that appears at the cone point and the size ...


Exploring Random Walks On Graphs For Protein Function Prediction, Angela M. Dahl 2018 Bowdoin College

Exploring Random Walks On Graphs For Protein Function Prediction, Angela M. Dahl

Honors Projects

No abstract provided.


The Doubly Stochastic Single Eigenvalue Problem: An Empirical Approach, John Wilkes, Charles Royal Johnson 2018 College of William & Mary

The Doubly Stochastic Single Eigenvalue Problem: An Empirical Approach, John Wilkes, Charles Royal Johnson

Undergraduate Honors Theses

The doubly stochastic single eigenvalue problem asks what is the set DSn of all complex numbers that occur as an eigenvalue of an n-by-n doubly stochastic matrix. For n < 5, this set is known and for the analogous set for (singly) stochastic matrices, the set is known for all n. For Pk , the polygon formed by the k-th roots of unity, Unk=1 Pk ⊆ DSn, as is easily shown. For n < 5, this containment is an equality, but for n = 5, the containment is strict (though it is close). Presented here is substantial, computational evidence that the containment is an equality for 6 ≤ n ≤ 10 and for what DS5 actually is.


An Optimized Route For Q100'S Bert And Kristin To Visit All Jersey Mike's Subs In Atlanta For Charity, 2018 Kennesaw State University

An Optimized Route For Q100'S Bert And Kristin To Visit All Jersey Mike's Subs In Atlanta For Charity

Symposium of Student Scholars

The Bert Show is a popular morning show on Atlanta’s Q100 radio station. They host a non-profit organization that provides a “magical, all-expenses-paid, five-day journey to Walt Disney World for children with chronic and terminal illnesses and their families” called “Bert’s Big Adventure.” On March 28th, 2018, thirty-seven locations of Jersey Mike’s are participating in the their Jersey Mike’s Day of Giving to support Bert’s Big Adventure. The goal is to have two popular radio show hosts visit each of these locations for some photos and presence to draw in more customers! But how ...


Notes On The Proof Of The Van Der Waerden Permanent Conjecture, Vicente Valle Martinez 2018 Iowa State University

Notes On The Proof Of The Van Der Waerden Permanent Conjecture, Vicente Valle Martinez

Vicente Valle Martinez

The permanent of an $n\times n$ matrix $A=(a_{i j})$ with real entries is defined by the sum
$$\sum_{\sigma \in S_n} \prod_{i=1}^{n} a_{i \sigma(i)}$$
where $S_n$ denotes the symmetric group on the $n$-element set $\{1,2,\dots,n\}$.
In this creative component we survey some known properties of permanents, calculation of permanents for particular types of matrices and their applications in combinatorics and linear algebra. Then we follow the lines of van Lint's exposition of Egorychev's proof for the van der Waerden's conjecture on the permanents of doubly ...


On Passing The Buck, Adam J. Hammett, Anna Joy Yang 2018 Cedarville University

On Passing The Buck, Adam J. Hammett, Anna Joy Yang

The Research and Scholarship Symposium

Imagine there are n>1 people seated around a table, and person S starts with a fair coin they will flip to decide whom to hand the coin next -- if "heads" they pass right, and if "tails" they pass left. This process continues until all people at the table have "touched" the coin. Curiously, it turns out that all people seated at the table other than S have the same probability 1/(n-1) of being last to touch the coin. In fact, Lovasz and Winkler ("A note on the last new vertex visited by a random walk," J. Graph Theory ...


Generalizations Of The Strong Arnold Property And The Minimum Number Of Distinct Eigenvalues Of A Graph, Wayne Barrett, Shaun Fallat, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Bryan L. Shader 2018 Brigham Young University

Generalizations Of The Strong Arnold Property And The Minimum Number Of Distinct Eigenvalues Of A Graph, Wayne Barrett, Shaun Fallat, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Bryan L. Shader

Leslie Hogben

For a given graph G and an associated class of real symmetric matrices whose off- diagonal entries are governed by the adjacencies in G, the collection of all possible spectra for such matrices is considered. Building on the pioneering work of Colin de Verdiere in connection with the Strong Arnold Property, two extensions are devised that target a better understanding of all possible spectra and their associated multiplicities. These new properties are referred to as the Strong Spectral Property and the Strong Multiplicity Property. Finally, these ideas are applied to the minimum number of distinct eigenvalues associated with G, denoted ...


Applications Of Analysis To The Determination Of The Minimum Number Of Distinct Eigenvalues Of A Graph, Beth Bjorkman, Leslie Hogben, Scarlitte Ponce, Carolyn Reinhart, Theodore Tranel 2018 Iowa State University

Applications Of Analysis To The Determination Of The Minimum Number Of Distinct Eigenvalues Of A Graph, Beth Bjorkman, Leslie Hogben, Scarlitte Ponce, Carolyn Reinhart, Theodore Tranel

Leslie Hogben

We establish new bounds on the minimum number of distinct eigenvalues among real symmetric matrices with nonzero off-diagonal pattern described by the edges of a graph and apply these to determine the minimum number of distinct eigenvalues of several families of graphs and small graphs.


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

Leslie Hogben

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


The Relationship Between K-Forcing And K-Power Domination, Daniela Ferrero, Leslie Hogben, Franklin H.J. Kenter, Michael Young 2018 Texas State University

The Relationship Between K-Forcing And K-Power Domination, Daniela Ferrero, Leslie Hogben, Franklin H.J. Kenter, Michael Young

Leslie Hogben

Zero forcing and power domination are iterative processes on graphs where an initial set of vertices are observed, and additional vertices become observed based on some rules. In both cases, the goal is to eventually observe the entire graph using the fewest number of initial vertices. The concept of k-power domination was introduced by Chang et al. (2012) as a generalization of power domination and standard graph domination. Independently, k-forcing was defined by Amos et al. (2015) to generalize zero forcing. In this paper, we combine the study of k-forcing and k-power domination, providing a new approach to analyze both ...


Zero Forcing And Power Domination For Graph Products, Katherine F. Benson, Daniela Ferrero, Mary Flagg, Veronika Furst, Leslie Hogben, Violeta Vasilevska, Brian Wissman 2018 Westminster College - Fulton

Zero Forcing And Power Domination For Graph Products, Katherine F. Benson, Daniela Ferrero, Mary Flagg, Veronika Furst, Leslie Hogben, Violeta Vasilevska, Brian Wissman

Leslie Hogben

The power domination number arose from the monitoring of electrical networks, and methods for its determination have the associated application. The zero forcing number arose in the study of maximum nullity among symmetric matrices described by a graph (and also in control of quantum systems and in graph search algorithms). There has been considerable effort devoted to the determination of the power domination number, the zero forcing number, and maximum nullity for specific families of graphs. In this paper we exploit the natural relationship between power domination and zero forcing to obtain results for the power domination number of tensor ...


On Structures Of Large Rooted Graphs, Shilin Wang 2018 Louisiana State University and Agricultural and Mechanical College

On Structures Of Large Rooted Graphs, Shilin Wang

LSU Doctoral Dissertations

A rooted graph is a pair (G,R), where G is a graph and R⊆V(G). There are two research topics in this thesis. One is about unavoidable substructures in sufficiently large rooted graphs. The other is about characterizations of rooted graphs excluding specific large graphs.

The first topic of this thesis is motivated by Ramsey Theorem, which states that K_n and ¯(K_n ) are unavoidable induced subgraphs in every sufficiently large graph. It is also motivated by a classical result of Oporowski, Oxley, and Thomas, which determines unavoidable large 3-connected minors. We first determine unavoidable induced subgraphs, and unavoidable ...


Characterizing Graphs Of Maximum Principal Ratio, Michael Tait, Josh Tobin 2018 Carnegie Mellon University

Characterizing Graphs Of Maximum Principal Ratio, Michael Tait, Josh Tobin

Electronic Journal of Linear Algebra

The principal ratio of a connected graph, denoted γ(G), is the ratio of the maximum and minimum entries of its Perron eigenvector. Cioaba and Gregory (2007) conjectured that the graph on n vertices maximizing γ(G) is a kite graph, that is, a complete graph with a pendant path. In this paper, their conjecture is proved


Vertex-Relaxed Graceful Labelings Of Graphs And Congruences, Florin Aftene 2018 Western Kentucky University

Vertex-Relaxed Graceful Labelings Of Graphs And Congruences, Florin Aftene

Masters Theses & Specialist Projects

A labeling of a graph is an assignment of a natural number to each vertex

of a graph. Graceful labelings are very important types of labelings. The study of graceful labelings is very difficult and little has been shown about such labelings. Vertex-relaxed graceful labelings of graphs are a class of labelings that include graceful labelings, and their study gives an approach to the study of graceful labelings. In this thesis we generalize the congruence approach of Rosa to obtain new criteria for vertex-relaxed graceful labelings of graphs. To do this, we generalize Faulhaber’s Formula, which is a famous ...


Runs Of Identical Outcomes In A Sequence Of Bernoulli Trials, Matthew Riggle 2018 Western Kentucky University

Runs Of Identical Outcomes In A Sequence Of Bernoulli Trials, Matthew Riggle

Masters Theses & Specialist Projects

The Bernoulli distribution is a basic, well-studied distribution in probability. In this thesis, we will consider repeated Bernoulli trials in order to study runs of identical outcomes. More formally, for t ∈ N, we let Xt ∼ Bernoulli(p), where p is the probability of success, q = 1 − p is the probability of failure, and all Xt are independent. Then Xt gives the outcome of the tth trial, which is 1 for success or 0 for failure. For n, m ∈ N, we define Tn to be the number of trials needed to first observe n consecutive successes (where the nth ...


Controllability And Observability Of The Discrete Fractional Linear State-Space Model, Duc M. Nguyen 2018 Western Kentucky University

Controllability And Observability Of The Discrete Fractional Linear State-Space Model, Duc M. Nguyen

Masters Theses & Specialist Projects

This thesis aims to investigate the controllability and observability of the discrete fractional linear time-invariant state-space model. First, we will establish key concepts and properties which are the tools necessary for our task. In the third chapter, we will discuss the discrete state-space model and set up the criteria for these two properties. Then, in the fourth chapter, we will attempt to apply these criteria to the discrete fractional model. The general flow of our objectives is as follows: we start with the first-order linear difference equation, move on to the discrete system, then the fractional difference equation, and finally ...


The Hafnian And A Commutative Analogue Of The Grassmann Algebra, Dmitry Efimov 2018 Department of Mathematics, Komi Science Centre UD RAS

The Hafnian And A Commutative Analogue Of The Grassmann Algebra, Dmitry Efimov

Electronic Journal of Linear Algebra

A close relationship between the determinant, the pfaffian, and the Grassmann algebra is well-known. In this paper, a similar relation between the permanent, the hafnian, and a commutative analogue of the Grassmann algebra is described. Using the latter, some new properties of the hafnian are proved.


On Facial Unique-Maximum (Edge-)Coloring, Vesna Andova, Bernard Lidicky, Borut Luzar, Riste Skrekovski 2018 Ss Cyril and Methodius University

On Facial Unique-Maximum (Edge-)Coloring, Vesna Andova, Bernard Lidicky, Borut Luzar, Riste Skrekovski

Mathematics Publications

A facial unique-maximum coloring of a plane graph is a vertex coloring where on each face α the maximal color appears exactly once on the vertices of α. If the coloring is required to be proper, then the upper bound for the minimal number of colors required for such a coloring is set to 5. Fabrici and Göring [5] even con- jectured that 4 colors always suffice. Confi the conjecture would hence give a considerable strengthening of the Four Color Theorem. In this paper, we prove that the conjecture holds for subcubic plane graphs, outerplane graphs and plane quadrangulations. Additionally ...


A Counterexample To A Conjecture On Facial Unique-Maximal Colorings, Bernard Lidicky, Kacy Messerschmidt, Riste Skrekovski 2018 Iowa State University

A Counterexample To A Conjecture On Facial Unique-Maximal Colorings, Bernard Lidicky, Kacy Messerschmidt, Riste Skrekovski

Mathematics Publications

A facial unique-maximum coloring of a plane graph is a proper vertex coloring by natural numbers where on each face α the maximal color appears exactly once on the vertices of α. Fabrici and Göring [4] proved that six colors are enough for any plane graph and conjectured that four colors suffice. This conjecture is a strengthening of the Four Color theorem. Wendland [6] later decreased the upper bound from six to five. In this note, we disprove the conjecture by giving an infinite family of counterexamples. s we conclude that facial unique-maximum chromatic number of the sphere is five.


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


Digital Commons powered by bepress