Graph rigidity properties of Ramanujan graphs

DOI10.37236/11324zbMath1519.05151arXiv2206.03983OpenAlexW4385359983MaRDI QIDQ6133153

Georg Grasegger, Xiaofeng Gu, Sean Dewar, Sebastian M. Cioabă

Publication date: 18 August 2023

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

eigenvaluerigidityconnectivityalgebraic connectivityglobal rigidityredundant rigidity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Connectivity (05C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fractional spanning tree packing, forest covering and eigenvalues
• Edge-disjoint spanning trees and eigenvalues of regular graphs
• Large matchings from eigenvalues
• Spectral conditions for edge connectivity and packing spanning trees in multigraphs
• Generic global rigidity of body-hinge frameworks
• The generic rank of body-bar-and-hinge frameworks
• Matchings in regular graphs from eigenvalues
• A sufficient connectivity condition for generic rigidity in the plane
• Eigenvalues and edge-connectivity of regular graphs
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Explicit construction of linear sized tolerant networks
• Ramanujan graphs
• On the second eigenvalue of a graph
• Fractional arboricity, strength, and principal partitions in graphs and matroids
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Connected rigidity matroids and unique realizations of graphs
• Connectivity and edge-disjoint spanning trees
• Large incidence-free sets in geometries
• Spectral conditions for graph rigidity in the Euclidean plane
• Extremal graphs for a spectral inequality on edge-disjoint spanning trees
• A census of small transitive groups and vertex-transitive graphs
• Note on edge-disjoint spanning trees and eigenvalues
• Global rigidity of generic frameworks on the cylinder
• Edge-disjoint spanning trees and eigenvalues
• Generic global rigidity
• On graphs and rigidity of plane skeletal structures
• Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs
• On the Problem of Decomposing a Graph into n Connected Factors
• On Moore Graphs with Diameters 2 and 3
• Edge-Disjoint Spanning Trees of Finite Graphs
• The 2-dimensional rigidity of certain families of graphs
• Edge-Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs
• Characterizing generic global rigidity
• Optimal attack and reinforcement of a network
• On Generic Rigidity in the Plane
• Conditions for Unique Graph Realizations
• The Rigidity of Graphs
• Spanning Rigid Subgraph Packing and Sparse Subgraph Covering
• Rigidity of Frameworks Supported on Surfaces
• A Characterization of Generically Rigid Frameworks on Surfaces of Revolution

This page was built for publication: Graph rigidity properties of Ramanujan graphs