# Discrete Mathematics and Combinatorics Commons™

## All Articles in Discrete Mathematics and Combinatorics

961 full-text articles. Page 6 of 36.

On Some Geometry Of Graphs, 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 ...

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, 2018 College of William & Mary

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

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.

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

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

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

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