Abstract:Let $G$ be a graph and $r \ge 1$. A vertex subset is $r$-independent if every connected component of its induced subgraph has size at most $r$. The family of all such subsets forms a simplicial complex, the $r$-independence complex $\Ind_r(G)$, generalizing the classical independence complex.
Recent work has focused on shellability and vertex decomposability of these complexes. For chordal graphs, $\Ind_r(G)$ has the homotopy type of a wedge of spheres for all $r$, and some chordal subfamilies are known where these complexes are not even sequentially Cohen-Macaulay. Thus, determining chordal graph classes and values of $r$ for which $\Ind_r(G)$ is sequentially Cohen-Macaulay, shellable, or vertex decomposable remains an active area. Existing methods, based on chordal hypergraphs or special graph properties, do not extend to arbitrary chordal graphs.
In this paper, we show that for every tree $T$ and every integer $r \ge 1$, the complex $\Ind_r(T)$ is vertex decomposable, resolving a conjecture \cite[Conjecture 3.15]{PD23chordal} of Abdelmalek et al. Our approach gives a structural description of shedding vertices via rooted subtrees and uses it to prove vertex decomposability recursively.
| Comments: | 16 pages, 2 figures, comments are welcome |
| Subjects: | Combinatorics (math.CO) |
| MSC classes: | 05E45, 05C76, 55U10, 05C05 |
| Cite as: | arXiv:2605.25150 [math.CO] |
| (or arXiv:2605.25150v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25150 arXiv-issued DOI via DataCite (pending registration) |
From: Rutuja Sawant [view email]
[v1]
Sun, 24 May 2026 16:05:51 UTC (15 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。