Rigidity and Separation Indices of Graphs in Surfaces |
| |
Authors: | Gašper Fijavž Bojan Mohar |
| |
Institution: | 1. Faculty of Computer and Information Science, University of Ljubljana, Ljubljana, Slovenia 2. Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|