On the clique behavior of graphs of low degree

DOI10.1007/S40590-022-00438-3MaRDI QIDQ2141759zbMATH OpenOpenAlexFDO

Authors Rafael Villarroel-Flores

Publication date 25 May 2022

Published in Boletín de la Sociedad Matemática Mexicana. Third Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.02483

zbMATH Keywords

convergent graphsiterated clique graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Graph operations (line graphs, products, etc.) (05C76)

Abstract: To any simple graph $G$, the clique graph operator $K$ associates 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 $ngeq1$. If there are $m<n$ such that $K^m(G)$ is isomorphic to $K^n(G)$ we say that $G$ is convergent, otherwise, $G$ is divergent. The first example of a divergent graph was shown by Neumann-Lara in the 1970s, and is the graph of the octahedron. In this paper, we prove that among the connected graphs with maximum degree 4, the octahedron is the only one that is divergent.

Recommendations

• Clique divergent graphs with unbounded sequence of diameters
• On clique divergent graphs with linear growth
• Clique dynamics of locally cyclic graphs with \(\delta \geq 6\)
• Convergence of iterated clique graphs
• A family of clique divergent graphs with linear growth

Cites work

• scientific article; zbMATH DE number 3641500 (Why is no real title available?)
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• scientific article; zbMATH DE number 851097 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Clique divergent graphs with unbounded sequence of diameters
• Clique‐convergence is undecidable for automatic graphs
• Edge contraction and edge removal on iterated clique graphs
• Graph relations, clique divergence and surface triangulations
• Locally \(C_6\) graphs are clique divergent
• On expansive graphs
• On hereditary clique-Helly self-clique graphs
• The clique operator on circular-arc graphs
• The clique operator on cographs and serial graphs
• The clique operator on matching and chessboard graphs
• Whitney triangulations, local girth and iterated clique graphs
• Über iterierte Clique-Graphen

Cited in

(17)

• Clique-divergence is not first-order expressible for the class of finite graphs.
• The images of the clique operator and its square are different
• On the clique behavior of circulants with three small jumps
• On the clique behavior of graphs with small constant link.
• The number of convergent graphs under the biclique operator with no twin vertices is finite
• Characterising clique convergence for locally cyclic graphs of minimum degree \(\delta \geq 6\)
• On the homotopy type of the iterated clique graphs of low degree
• Clique dynamics of locally cyclic graphs with \(\delta \geq 6\)
• Embedding clique-factors in graphs with low -independence number
• Edge contraction and edge removal on iterated clique graphs
• The clique graphs of the hexagonal lattice -- an explicit construction and a short proof of divergence
• Iterated clique graphs and bordered compact surfaces
• A new family of expansive graphs
• On the edge‐biclique graph and the iterated edge‐biclique operator
• Whitney triangulations, local girth and iterated clique graphs
• The icosahedron is clique divergent
• The clique behavior of circulants with three small jumps.

This page was built for publication: On the clique behavior of graphs of low degree

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