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.
From: Cathy Kriloff [view email]
[v1]
Mon, 22 Dec 2025 22:38:06 UTC (24 KB)
[v2]
Tue, 6 Jan 2026 18:11:50 UTC (27 KB)
[v3]
Mon, 16 Mar 2026 21:20:59 UTC (27 KB)
[v4]
Wed, 5 Aug 2026 20:48:37 UTC (27 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。