Back to search

Virginia Commonwealth University

Investigations in the semi-strong product of graphs and bootstrap percolation

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematical Sciences

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • McCall, Kevin J
Contributors dc:contributor
  • Ghidewon Abay-Asmerom

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • © The Author

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Virginia Commonwealth University
Base URL
scholarscompass.vcu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

McCall, Kevin J. Investigations in the semi-strong product of graphs and bootstrap percolation. Dissertation thesis, https://doi.org/10.25772/0FN2-VX93