论文标题
在低度的迭代集团图的同型类型上
On the homotopy type of the iterated clique graphs of low degree
论文作者
论文摘要
对于任何简单的graph \（g \），clique Graph Operator \（k \）分配了图\（k（g）\），这是\（g \）的最大完整子图的相交图。迭代的集团图由\（k^{0}（g）= g \）和\（k^{n}（g）= k（k^{n-1}（g））\（n \ geq 1 \）。我们通过\（g \）的完整子图的简单复合物\（\ mathrm {cl}（g）\）将拓扑概念与图相关联。因此，我们说图形\（g_ {1} \）和\（g_ {2} \）是同质的，每当\（\ mathrm {clrm {cl}（g_ {1}）\ \ \ \）和\（\ mathrm {cl}（cl}（g_ {2}）（g_ {2}）\）\（g_ {1}）\（一个图形\（k^{n}（g）\ simeq g \）的图\（n \ geq1 \）被称为\ emph {\（k \） - 同型永久}。如果\（g \）的最大完整子图的集合具有Helly属性，则图为\ emph {helly}。令\（g \）为helly图。 Escalante（1973）证明\（k（g）\）是helly，而Prisner（1992）证明\（g \ simeq k（g）\），因此helly图是\（k \） - 同型永久。我们猜想，如果图\（g \）满足\（k^{m}（g）\）对某些\（m \ geq1 \），则\（g \）为\（k \） - 同型永久。如果连接的图最多具有最大度，并且与八面体图不同，我们说它是\ emph {低度图}。最近证明，所有低度图\（g \）满足\（k^{2}（g）\）都是helly。在本文中，我们表明所有低度图具有楔形或圆周的同质类型，并且它们是\（k \） - 同型永久性。
To any simple graph \(G\), the clique graph operator \(K\) assigns the graph \(K(G)\) which is the intersection graph of the maximal complete subgraphs of \(G\). The iterated clique graphs are defined by \(K^{0}(G)=G\) and \(K^{n}(G)=K(K^{n-1}(G))\) for \(n\geq 1\). We associate topological concepts to graphs by means of the simplicial complex \(\mathrm{Cl}(G)\) of complete subgraphs of \(G\). Hence we say that the graphs \(G_{1}\) and \(G_{2}\) are homotopic whenever \(\mathrm{Cl}(G_{1})\) and \(\mathrm{Cl}(G_{2})\) are. A graph \(G\) such that \(K^{n}(G)\simeq G\) for all \(n\geq1\) is called \emph{\(K\)-homotopy permanent}. A graph is \emph{Helly} if the collection of maximal complete subgraphs of \(G\) has the Helly property. Let \(G\) be a Helly graph. Escalante (1973) proved that \(K(G)\) is Helly, and Prisner (1992) proved that \(G\simeq K(G)\), and so Helly graphs are \(K\)-homotopy permanent. We conjecture that if a graph \(G\) satisfies that \(K^{m}(G)\) is Helly for some \(m\geq1\), then \(G\) is \(K\)-homotopy permanent. If a connected graph has maximum degree at most four and is different from the octahedral graph, we say that it is a \emph{low degree graph}. It was recently proven that all low degree graphs \(G\) satisfy that \(K^{2}(G)\) is Helly. In this paper, we show that all low degree graphs have the homotopy type of a wedge or circumferences, and that they are \(K\)-homotopy permanent.
