Rigidity and Separation Indices of Graphs in Surfaces

摘要

Let Σ be a surface. We prove that rigidity indices of graphs which admit a polyhedral embedding in Σ and 5-connected graphs admitting an embedding in Σ are bounded by a constant depending on Σ. Moreover if the Euler characteristic of Σ is negative, then the separation index of graphs admitting a polyhedral embedding in Σ is also bounded. As a side result we show that distinguishing number of both Σ-polyhedral and 5-connected graphs which admit and embedding in Σ is also bounded.