论文标题
线图集合复合物的代数特性
Algebraic Properties of Clique Complexes of Line Graphs
论文作者
论文摘要
令$ h $为一个简单的无向图，$ g = \ mathrm {l}（h）$是其线路图。假设$δ（g）$表示$ g $的集团综合体。我们表明，$δ（g）$是依次是cohen-macaulay，并且仅当它是可壳的，并且仅当它是可以分解的时。此外，如果$δ（g）$是纯净的，我们证明这些条件也等同于紧密连接。此外，我们陈述了$δ（g）$的$ H $的完整特征，是Cohen-Macaulay，依次是Cohen-Macaulay或Gorenstein。我们使用这些特征来呈现使用图$ g $的线性时间算法，检查$ g $是线图，如果是的，请确定$δ（g）$是Cohen-Macaulay还是顺序cohen-Macaulay或Gorenstein。
Let $H$ be a simple undirected graph and $G=\mathrm{L}(H)$ be its line graph. Assume that $Δ(G)$ denotes the clique complex of $G$. We show that $Δ(G)$ is sequentially Cohen-Macaulay if and only if it is shellable if and only if it is vertex decomposable. Moreover if $Δ(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 $Δ(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 $Δ(G)$ is Cohen-Macaulay or sequentially Cohen-Macaulay or Gorenstein.
