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

DOI10.1002/JGT.22913zbMATH Open1522.05082arXiv2202.03965OpenAlexW4312124065MaRDI QIDQ6074574FDOQ6074574

Authors: Sean Dewar 

Publication date: 12 October 2023

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Connected rigidity matroids and unique realizations of graphs
• Generic global rigidity
• Characterizing generic global rigidity
• Title not available (Why is that?)
• On Generic Rigidity in the Plane
• The Rigidity of Graphs
• Title not available (Why is that?)
• Connectivity of transitive graphs
• The vertex-connectivity of a distance-regular graph
• The distance-regular graphs of valency four
• The 2-dimensional rigidity of certain families of graphs
• 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)