Graph Sensitivity under Join and Decomposition

2025/12/22 by Cathy Kriloff, Kriloff, Cathy, Jacob Tolman +1
Computer Science · Mathematics · #05C76 (Primary) 05C75 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · doi:10.48550/arxiv.2512.19915

openalex publication_date 2025/12/22 · openalex created_date 2025/12/25 · openalex updated_date 2026/07/28

Abstract

The sensitivity, σ(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 Δ(G_n) → ∞ as n → ∞ sensitive if σ(G_n) → ∞, 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.

Citations

• Sensitivity and Hamming graphs
• On induced subgraphs of H(n,3) with maximum degree 1
• On prime Cayley graphs
• On Induced Subgraph of Cartesian Product of Paths
• Hat guessing number of planar graphs is at least 22
• An induced subgraph of the Hamming graph with maximum degree 1
• (α, β)-Modules in Graphs
• On sensitivity in bipartite Cayley graphs
• A Conjecture on Induced Subgraphs of Cayley Graphs
• Induced subgraphs of product graphs and a generalization of Huang's theorem
• On Induced Subgraphs of the Hamming Graph
• Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
• The Critical Independence Number and an Independence Decomposition
• A survey on algorithmic aspects of modular decomposition

Related

• Sensitivity and Hamming graphs
• Lower bounds for sensitivity of graph properties
• Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
• On Induced Subgraphs of the Hamming Graph
• Extremal Threshold Graphs for Matchings and Independent Sets