Graph Sensitivity under Join and Decomposition

Abstract

The sensitivity, $\sigma (G)$, of a finite undirected simple graph $G$ is the smallest maximum degree of an induced subgraph on more than the maximum number of independent vertices. Call an indexed family of graphs $G_n$, with maximum degree $\Delta (G_n)\to \infty$ as $n\to \infty$, sensitive if $\sigma (G_n)\to \infty$ and insensitive otherwise. We describe sensitivity under the join operation and decomposition into stable blocks and construct sensitive and insensitive, primarily non-regular, graph families. We determine the sensitivity explicitly for numerous singly- and doubly-indexed graph families, including certain generalized joins - e.g., complete multipartite graphs and some generalized windmill graphs; general rooted products; and families of corona graphs.

22 pages, 1 figure; v4: fixed cleveref issue, typo in Figure 1, and references [2] and [30]; v3: includes several small corrections/changes resulting from the change to Definitions 2.2 and 2.7; v2: changed Definitions 2.2 and 2.7 with attribution and verified no consequential changes; minor edits - especially to improve the proof of Theorem 3.1; questions or comments welcome