Classifying the globally rigid edge‐transitive graphs and distance‐regular graphs in the plane

DOI10.1002/JGT.22913MaRDI QIDQ6074574zbMATH OpenOpenAlexFDO

Authors Sean Dewar

Publication date 12 October 2023

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

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

zbMATH Keywords

rigiditydistance-regular graphsedge-transitive graphsglobal rigidity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: A graph is said to be globally rigid if almost all embeddings of the graph's vertices in the Euclidean plane will define a system of edge-length equations with a unique (up to isometry) solution. In 2007, Jackson, Servatius and Servatius characterised exactly which vertex-transitive graphs are globally rigid solely by their degree and maximal clique number, two easily computable parameters for vertex-transitive graphs. In this short note we will extend this characterisation to all graphs that are determined by their automorphism group. We do this by characterising exactly which edge-transitive graphs and distance-regular graphs are globally rigid by their minimal and maximal degrees.

Recommendations

• The 2-dimensional rigidity of certain families of graphs
• Spectral conditions for graph rigidity in the Euclidean plane
• Minimally globally rigid graphs
• Sufficient conditions for the global rigidity of graphs
• Graph rigidity properties of Ramanujan graphs

Cites work

• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 2188749 (Why is no real title available?)
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Characterizing generic global rigidity
• Connected rigidity matroids and unique realizations of graphs
• Connectivity of transitive graphs
• Generic global rigidity
• On Generic Rigidity in the Plane
• The 2-dimensional rigidity of certain families of graphs
• The Rigidity of Graphs
• The distance-regular graphs of valency four
• The vertex-connectivity of a distance-regular graph
• There are only finitely many distance-regular graphs of fixed valency greater than two

This page was built for publication: Classifying the globally rigid edge‐transitive graphs and distance‐regular graphs in the plane

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