Clique‐convergence is undecidable for automatic graphs. Issue 3 (7th October 2020)

• Record Type: Journal Article
• Authors: Cedillo, C.; Pizaña, M. A.
• Is Part Of: Journal of graph theory. Volume 96:Issue 3(2021)
• Page Start: 414
• Page End: 437
• Publication Date: 2020-10-07
• Subjects: automatic structures -- clique graphs -- decidability -- graph dynamics -- graph theory; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22622
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: The clique operator transforms a graph G into its clique graph K ( G ), which is the intersection graph of all the (maximal) cliques of G . Iterated clique graphs are then defined by K n ( G ) = K ( K n − 1 ( G ) ), K 0 ( G ) = G . If there are some n ≠ m such that K n ( G ) ≅ K m ( G ), then we say that G is clique‐convergent . The clique graph operator and iterated clique graphs have been studied extensively, but no characterization for clique‐convergence has been found so far. Automatic graphs are (not necessarily finite) graphs whose vertices and edges can be recognized by finite automata. Automatic graphs (and automatic structures ) have strong decidability properties inherited from the finite automata defining them. Here we prove that clique‐convergence is algorithmically undecidable for the class of automatic graphs. Moreover, the problem remains undecidable, if we reduce to the class that contain only quasi‐clique‐Helly and bounded degree graphs. As a consequence, it follows that clique‐convergence for automatic graphs is not first‐order expressible.