Discrete Mathematics and Combinatorics Commons^™

Failed Zero Forcing Numbers Of Trees And Circulant Graphs, Luis Gomez, Karla Rubi, Jorden Terrazas, Rigoberto Florez, Darren A. Narayan

Theory & Applications of Graphs

Given a graph $G$, the zero forcing number of $G$, $Z(G)$, is the smallest cardinality of any set $S$ of vertices on which repeated applications of the forcing rule (described below) results in all vertices being in $S$. The forcing rule is as follows: if a vertex $v$ is in $S$, and exactly one neighbor $u$ of $v$ is not in $S$, then $u$ is added to $S$ in the next iteration. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied. The zero forcing number is used to study the maximum nullity/minimum …

Measuring The Similarity Between Trees Of Different Order, Camilo Morales

HMC Senior Theses

Graphs encode relationships between data. However, due to their versatility, it is often difficult to generalize the notion of similarity between two graphs using a distance function. Since graphs can represent various data sets, specific distance metrics need to be tailored for questions we are interested in answering or the data set we are working with. This project is motivated by ongoing investigations into the evolution of female gender representation in mathematics. By building off previous work that has taken data from the Mathematics Genealogy Project and modeled this evolution of representation via a tree, we would like to develop …

The Forget Time For Random Walks On Trees Of A Fixed Diameter, Lola R. Vescovo

Mathematics, Statistics, and Computer Science Honors Projects

A mixing measure is the expected length of a random walk on a graph given a set of starting and stopping conditions. We study a mixing measure called the forget time. Given a graph G, the pessimal access time for a target distribution is the expected length of an optimal stopping rule to that target distribution, starting from the worst initial vertex. The forget time of G is the smallest pessimal access time among all possible target distributions. We prove that the balanced double broom maximizes the forget time on the set of trees on n vertices with diameter …

Problems In Chemical Graph Theory Related To The Merrifield-Simmons And Hosoya Topological Indices, William B. O'Reilly

College of Graduate Studies: Theses & Dissertations

In some sense, chemical graph theory applies graph theory to various physical sciences. This interdisciplinary field has significant applications to structure property relationships, as well as mathematical modeling. In particular, we focus on two important indices widely used in chemical graph theory, the Merrifield-Simmons index and Hosoya index. The Merrifield-Simmons index and the Hosoya index are two well-known topological indices used in mathematical chemistry for characterizing specific properties of chemical compounds. Substantial research has been done on the two indices in terms of enumerative problems and extremal questions. In this thesis, we survey known extremal results and consider the generalized …

Counting Power Domination Sets In Complete M-Ary Trees, Hays Whitlatch, Katharine Shultis, Olivia Ramirez, Michele Ortiz, Sviatlana Kniahnitskaya

Theory & Applications of Graphs

Motivated by the question of computing the probability of successful power domination by placing k monitors uniformly at random, in this paper we give a recursive formula to count the number of power domination sets of size k in a labeled complete m-ary tree. As a corollary we show that the desired probability can be computed in exponential with linear exponent time.

Harmonious Labelings Via Cosets And Subcosets, Jared L. Painter, Holleigh C. Landers, Walker M. Mattox

Theory & Applications of Graphs

In [Abueida, A. and Roblee, K., More harmonious labelings of families of disjoint unions of an odd cycle and certain trees, J. Combin. Math. Combin. Comput., 115 (2020), 61-68] it is shown that the disjoint union of an odd cycle and certain paths is harmonious, and that certain starlike trees are harmonious using properties of cosets for a particular subgroup of the integers modulo m, where m is the number of edges of the graph. We expand upon these results by first exploring the numerical properties when adding values from cosets and subcosets in the integers modulo m. …

Iterated Line Graphs On Bi-Regular Graphs And Trees, Brenden Balch

Rose-Hulman Undergraduate Mathematics Journal

In 1965, van Rooij and Wilf considered sequences of line graphs, in which they grouped sequences of line graphs into four categories. We’ll add to their research by presenting results on sequences of line graphs for star graphs and bi-regular graphs. We will then investigate slight variations of star graphs.

Merge Trees In Discrete Morse Theory, Benjamin Johnson

Mathematics Summer Fellows

The field of topological data analysis seeks to use techniques in topology to study large data sets. The hope is that rather than single quantities that summarize the data, such as mean or standard deviation, information about the data can be learned by studying the overall ``shape” of the data. One way to summarize this data is through a merge tree. Merge trees can be thought of as keeping track of certain clusters of data and determining when they merge together. In this paper, we will study merge trees induced by a discrete Morse function on a tree. Under a …

Graph Invariants Of Trees With Given Degree Sequence, Rachel Bass

College of Graduate Studies: Theses & Dissertations

Graph invariants are functions defined on the graph structures that stay the same under taking graph isomorphisms. Many such graph invariants, including some commonly used graph indices in Chemical Graph Theory, are defined on vertex degrees and distances between vertices. We explore generalizations of such graph indices and the corresponding extremal problems in trees. We will also briefly mention the applications of our results.

Two Rosa-Type Labelings Of Uniform K-Distant Trees And A New Class Of Trees, Kimberly Wenger Diller

Honors Projects

A k-distant tree consists of a main path, called the spine, such that each vertex on the spine is joined by an edge to an end-vertex of at most one path on at most k vertices. Those paths, along with the edge joining them to the spine, are called tails. When every vertex on the spine has exactly one incident tail of length k we call the tree a uniform k-distant tree. We show that every uniform k-distant tree admits both a graceful- and an α-labeling.

For a graph G and a positive integer …

Path-Tables Of Trees: A Survey And Some New Results, Kevin Asciak

Theory & Applications of Graphs

The (vertex) path-table of a tree Τ contains quantitative information about the paths in Τ. The entry (i,j) of this table gives the number of paths of length j passing through vertex ^vi. The path-table is a slight variation of the notion of path layer matrix. In this survey we review some work done on the vertex path-table of a tree and also introduce the edge path-table. We show that in general, any type of path-table of a tree Τ does not determine Τ uniquely. We shall show that in trees, the number of paths passing through …

Constructions And Enumeration Methods For Cubic Graphs And Trees, Erica R. Gilliland

Undergraduate Honors Thesis Collection

The goal of this thesis is to study two related problems that, in the broadest terms, lie in a branch of mathematics called graph theory. The first problem examines some new techniques for constructing a Hamilton graph of least possible order and having a preassigned girth, and the second concerns the enumeration of a certain type of graphs called trees.

Enumeration Of Matchings In The Incidence Graphs Of Complete And Complete Bipartite Graphs, Nicholas Pippenger

All HMC Faculty Publications and Research

If G = (V, E) is a graph, the incidence graphI(G) is the graph with vertices I ∪ E and an edge joining v ∈ V and e ∈ E when and only when v is incident with e in G. For G equal to K_n (the complete graph on n vertices) or K_n,n (the complete bipartite graph on n + n vertices), we enumerate the matchings (sets of edges, no two having a vertex in common) in I(G), both exactly (in terms of generating …

Enumeration Of Equicolourable Trees, Nicholas Pippenger

All HMC Faculty Publications and Research

A tree, being a connected acyclic graph, can be bicolored in two ways, which differ from each other by exchange of the colors. We shall say that a tree is equicolorable if these bicolorings assign the two colors to equal numbers of vertices. Labelled equicolored trees have been enumerated several times in the literature, and from this result it is easy to enumerate labelled equicolorable trees. The result is that the probability that a randomly chosen n-vertex labelled tree is equicolorable is asymptotically just twice the probability that its vertices would be equicolored if they were assigned colors by …