Date of Award
12-2025
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Mathematical Sciences
Committee Chair/Advisor
Wayne Goddard
Committee Member
Michael Henning
Committee Member
Beth Novick
Committee Member
Svetlana Poznanovik
Abstract
In 2015, Caro and Hansberg introduced a wonderful and natural generalization of the well-studied parameter of domination in graphs. For a graph $G$ and a family of graphs $\FF$, they define $S$ to be an $\FF$-isolating set if $G-N[S]$ contains no member of $\FF$ as a subgraph. The case where $\FF=\{K_1\}$ coincides with domination. The case where $\FF=\{K_2\}$ is now simply referred to as an isolating set. We strengthen known results about the isolation number of a graph, and explore variations of the parameter including the independent and total versions.
In particular for connected graphs of order $n$, a bound of $n/3$ for the isolation number of a graph was known along with a partial determination of the extremal family. We strengthen the bound by showing that (other than two exceptions) every connected graph has a partition of the vertex set into three disjoint isolating sets, and further we completely determine the extremal family. We also consider variations of the parameter including the total and independent versions. For the total version, we prove an upper bound of $n/2$ for all graphs other than $C_7$. For the independent version, we consider a few different families of graphs. Notably, we provide partitioning arguments to establish an upper bound of $n/3$ for bipartite graphs and $(n+1)/3$ for three-colorable graphs.
Lastly, we introduce the all-$k$-isolation number to be the case where $\FF$ is all trees of order~$k$. Thus the resultant $G-N[S]$ has no component of order at least~$k$. This gives another way to generalize domination and isolation, as the former corresponds to all-$1$-isolation and the latter to all-$2$-isolation. In trees, we prove an upper bound on both the independent and standard version of all-$k$-isolation, and completely determine the extremal families. This is surprising in that it implies that the structure of the forbidden tree is not important and that we need only worry about the order.
Recommended Citation
Boyer, Geoffrey, "On Variations of Isolation in Graphs" (2025). All Dissertations. 4100.
https://open.clemson.edu/all_dissertations/4100