DOI
https://doi.org/10.25772/0FN2-VX93
Defense Date
2023
Document Type
Dissertation
Degree Name
Doctor of Philosophy
Department
Mathematical Sciences
First Advisor
Ghidewon Abay-Asmerom
Abstract
The semi-strong product of graphs G and H is a way of forming a new graph from the graphs G and H. The vertex set of the semi-strong product is the Cartesian product of the vertex sets of G and H, V(G) x V(H). The edges of the semi-strong product are determined as follows: (g1,h1)(g2,h2) is an edge of the product whenever g1g2 is an edge of G and h1h2 is an edge of H or g1 = g2 and h1h2 is an edge of H.
A natural subject for investigation is to determine properties of the semi-strong product in terms of those properties of its factors. We investigate distance, independence, matching, and domination in the semi-strong product
Bootstrap Percolation is a process defined on a graph. We begin with an initial set of infected vertices. In each subsequent round, uninfected vertices become infected if they are adjacent to at least r infected vertices. Once infected, vertices remain infected. The parameter r is called the percolation threshold. When G is finite, the infection either stops at a proper subset of G or all of V(G) becomes infected. If all of V(G) eventually becomes infected, then we say that the infection percolates and we call the initial set of infected vertices a percolating set.
The cardinality of a minimum percolating set of G with percolation threshold r is denoted m(G,r). We determine m(G,r) for certain Kneser graphs and bipartite Kneser graphs.
Rights
© The Author
Is Part Of
VCU University Archives
Is Part Of
VCU Theses and Dissertations
Date of Submission
12-12-2023