Graph Sensitivity under Join and Decomposition
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908890596114432 |
|---|---|
| author | Kriloff, Cathy Tolman, Jacob |
| author_facet | Kriloff, Cathy Tolman, Jacob |
| contents | 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) \to \infty$ as $n \to \infty$ sensitive if $σ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_19915 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph Sensitivity under Join and Decomposition Kriloff, Cathy Tolman, Jacob Combinatorics 05C76 (Primary) 05C75 (Secondary) 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) \to \infty$ as $n \to \infty$ sensitive if $σ(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. |
| title | Graph Sensitivity under Join and Decomposition |
| topic | Combinatorics 05C76 (Primary) 05C75 (Secondary) |
| url | https://arxiv.org/abs/2512.19915 |