Higher independence complexes of graphs and their homotopy types

MaRDI QIDQ5003757zbMATH OpenFDO

Authors Priyavrat Deshpande, Anurag Singh

Publication date 29 July 2021

Full work available at URL https://arxiv.org/abs/2001.05448, http://www.mathjournals.org/jrms/2021-036-001/2021-036-001-007.html

zbMATH Keywords

\(r\)-independence complexeshomotopy typesimplicial complex

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial aspects of simplicial complexes (05E45) Classification of homotopy type (55P15) Relations of low-dimensional topology with graph theory (57M15)

Abstract: For $rgeq1$, the $r$-independence complex of a graph $G$ is a simplicial complex whose faces are subset $IsubseteqV(G)$ such that each component of the induced subgraph $G[I]$ has at most $r$ vertices. In this article, we determine the homotopy type of $r$-independence complexes of certain families of graphs including complete $s$-partite graphs, fully whiskered graphs, cycle graphs and perfect $m$-ary trees. In each case, these complexes are either homotopic to a wedge of equi-dimensional spheres or are contractible. We also give a closed form formula for their homotopy types.

Recommendations

• scientific article; zbMATH DE number 7499158
• Independence complexes of chordal graphs
• Distance \(r\)-domination number and \(r\)-independence complexes of graphs
• Chordal graphs, higher independence and vertex decomposable complexes
• scientific article; zbMATH DE number 1559018

Cites work

• A note on distance domination numbers of graphs
• Bounded monochromatic components for random graphs
• Certain homology cycles of the independence complex of grids
• Combinatorial algebraic topology
• Complexes of directed trees
• Defective and clustered graph colouring
• Distance domination and distance irredundance in graphs
• Domination numbers and homology
• Generalizations of independence and chromatic numbers of a graph
• Homotopy type of neighborhood complexes of Kneser graphs, \(KG_{2,k}\)
• scientific article; zbMATH DE number 6464016 (Why is no real title available?)
• Independence complexes of chordal graphs
• Matching and independence complexes related to small grids
• Morse theory for cell complexes
• On the \(r\)-domination number of a graph
• On the independence complex of square grids
• Proof of the Lovász conjecture
• Shellable graphs and sequentially Cohen-Macaulay bipartite graphs
• Simplicial complexes of graphs
• Star clusters in independence complexes of graphs
• The homology of ``\(k\)-equal manifolds and related partition lattices
• The topology of the independence complex
• Vertex decomposable graphs and obstructions to shellability
• Weighted sheaves and homology of Artin groups

Cited in

(31)

• Topology of complexes of edge covering partite graphs and hypergraphs
• Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs
• Homotopy type of circle graph complexes motivated by extreme Khovanov homology
• Distance \(r\)-domination number and \(r\)-independence complexes of graphs
• The homotopy type of the independence complex of graphs with no induced cycles of length divisible by 3
• Higher hairy graph homology
• Homotopy types of the Hom complexes of graphs
• Matching trees for simplicial complexes and homotopy type of devoid complexes of graphs
• scientific article; zbMATH DE number 5990556 (Why is no real title available?)
• scientific article; zbMATH DE number 7499158 (Why is no real title available?)
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• Star clusters in independence complexes of graphs
• Splittings of independence complexes and the powers of cycles
• On the homotopy types of the independence complexes of grid graphs with cylindrical identification
• scientific article; zbMATH DE number 1559018 (Why is no real title available?)
• Independence complexes and incidence graphs
• On the homology of independence complexes
• scientific article; zbMATH DE number 6464016 (Why is no real title available?)
• Independence complexes of comaximal graphs of commutative rings with identity
• Perfect matching complexes of honeycomb graphs
• Chordal graphs, higher independence and vertex decomposable complexes
• Dominance complexes and vertex cover numbers of graphs
• Independence complexes and edge covering complexes via Alexander duality
• Topology of cut complexes of graphs
• Homotopy type of the independence complex of some categorical products of graphs
• Perfect matching complexes of polygonal line tilings
• Graded Betti numbers of a hyperedge ideal associated to join of graphs
• Total cut complexes of graphs
• Fröberg's theorem, vertex splittability and higher independence complexes
• Topology of total cut complexes and cut complexes of grid graphs
• Independence complexes of chordal graphs

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Higher independence complexes of graphs and their homotopy types

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5003757)