Clique‐convergence is undecidable for automatic graphs

DOI10.1002/JGT.22622MaRDI QIDQ6055401zbMATH OpenFDO

Authors C. Cedillo, M. A. Pizaña

Publication date 29 September 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/JGT.22622

zbMATH Keywords

automatic structuresclique graphsdecidabilitygraph dynamics

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Clique-divergence is not first-order expressible for the class of finite graphs.
• On the iterated biclique operator
• Convergence of iterated clique graphs
• On clique divergent graphs with linear growth
• The clique operator on cographs and serial graphs

Cites work

• (Quantum) spacetime as a statistical geometry of lumps in random networks
• A geometric renormalization group in discrete quantum space–time
• Almost every graph is divergent under the biclique operator
• Automata Presenting Structures: A Survey of the Finite String Case
• Clique divergent clockwork graphs and partial orders
• Finite presentations of infinite structures: Automata and interpretations
• Graph theory with applications
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 851097 (Why is no real title available?)
• scientific article; zbMATH DE number 1409177 (Why is no real title available?)
• scientific article; zbMATH DE number 3402664 (Why is no real title available?)
• On self-clique graphs all of whose cliques have equal size.
• On self-clique shoal graphs
• Space-time as an order-parameter manifold in random networks and the emergence of physical points
• The dynamics of the line and path graph operators
• Über iterierte Clique-Graphen

Cited in

(4)

• On the clique behavior and Hellyness of the complements of regular graphs
• On the clique behavior of graphs of low degree
• Clique-divergence is not first-order expressible for the class of finite graphs.
• Characterising clique convergence for locally cyclic graphs of minimum degree \(\delta \geq 6\)

This page was built for publication: Clique‐convergence is undecidable for automatic graphs

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