Back to search

Clemson University

On Variations of Isolation in Graphs

Abstract

dc:description.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=\{K1\} coincides with domination. The case where \FF=\{K2\} 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 C7. 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.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Boyer, Geoffrey
Contributors dc:contributor
  • Wayne Goddard
  • Michael Henning
  • Beth Novick
  • Svetlana Poznanovik

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/4100

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Boyer, Geoffrey. On Variations of Isolation in Graphs. Dissertation thesis, https://open.clemson.edu/all_dissertations/4100