Clique‐convergence is undecidable for automatic graphs

DOI10.1002/JGT.22622zbMATH Open1521.05197MaRDI QIDQ6055401FDOQ6055401

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

Publication date: 29 September 2023

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

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

zbMATH Keywords

automatic structuresclique graphsdecidabilitygraph dynamics

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Über iterierte Clique-Graphen
• On self-clique shoal graphs
• Graph theory with applications
• Automata Presenting Structures: A Survey of the Finite String Case
• On self-clique graphs all of whose cliques have equal size.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Clique divergent clockwork graphs and partial orders
• Finite presentations of infinite structures: Automata and interpretations
• Space-time as an order-parameter manifold in random networks and the emergence of physical points
• (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
• The dynamics of the line and path graph operators

Cited In (4)

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

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)