Algebraic Properties of Clique Complexes of Line Graphs

MaRDI QIDQ6345847zbMATH OpenFDO

Authors Ashkan Nikseresht

Publication date 26 July 2020

Mathematics Subject Classification ID

Combinatorial aspects of commutative algebra (05E40) Combinatorial aspects of simplicial complexes (05E45) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55)

Abstract: Let $H$ be a simple undirected graph and $G=mathrmL(H)$ be its line graph. Assume that $Delta(G)$ denotes the clique complex of $G$. We show that $Delta(G)$ is sequentially Cohen-Macaulay if and only if it is shellable if and only if it is vertex decomposable. Moreover if $Delta(G)$ is pure, we prove that these conditions are also equivalent to being strongly connected. Furthermore, we state a complete characterizations of those $H$ for which $Delta(G)$ is Cohen-Macaulay, sequentially Cohen-Macaulay or Gorenstein. We use these characterizations to present linear time algorithms which take a graph $G$, check whether $G$ is a line graph and if yes, decide if $Delta(G)$ is Cohen-Macaulay or sequentially Cohen-Macaulay or Gorenstein.

This page was built for publication: Algebraic Properties of Clique Complexes of Line Graphs

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