Algebraic Properties of Clique Complexes of Line Graphs

arXiv2007.13082MaRDI QIDQ6345847FDOQ6345847

Authors: Ashkan Nikseresht 

Publication date: 26 July 2020

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.

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)

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)