Rigidity and Separation Indices of Graphs in Surfaces

被引：3

作者：

Fijavz, Gasper ^{[1
]}

Mohar, Bojan ^{[2
]}

机构：

[1] Univ Ljubljana, Fac Comp & Informat Sci, Ljubljana, Slovenia

[2] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada

来源：

GRAPHS AND COMBINATORICS | 2010年 / 26卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Separation index; Rigidity index; 5-Connected graph; Polyhedral embedding;

D O I：

10.1007/s00373-010-0929-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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

引用

页码：491 / 498

页数：8

共 11 条

[1] Albertson M.O., 1996, ELECT J COMBIN, V3
[2] Diestel R., 2005, GRAPH THEORY, VThird
[3] Rigidity and separation indices of Paley graphs
Fijavz, G
Mohar, B
[J]. DISCRETE MATHEMATICS, 2004, 289 (1-3) : 157 - 161
[4] Gross Jonathan L., 1987, Topological Graph Theory
[5] Hurwitz A., 1892, Math. Ann., V41, P403, DOI [10.1007/BF01443420, DOI 10.1007/BF01443420]
[6] Systems of curves on surfaces
Juvan, M
Malnic, A
Mohar, B
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 68 (01) : 7 - 22
[7] Flexibility of polyhedral embeddings of graphs in surfaces
Mohar, B
Robertson, N
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 83 (01) : 38 - 57
[8] Mohar B., 2001, JH STUD MATH SCI, DOI 10.56021/9780801866890
[9] Muzychuk M.E., 1987, VOPR TEOR GRUPP GOMO, V7, P64
[10] Negami S., DISTINGUISHING UNPUB

← 1 2 →