LIMIT POINTS FOR AVERAGE GENUS .1. 3-CONNECTED AND 2-CONNECTED SIMPLICIAL GRAPHS

被引:28
作者
CHEN, JN [1 ]
GROSS, JL [1 ]
机构
[1] COLUMBIA UNIV,DEPT COMP SCI,NEW YORK,NY 10027
关键词
D O I
10.1016/0095-8956(92)90033-T
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
It is demonstrated that a give value of average genus is shared by at most finitely many 2-connected simplicial graphs and by at most finitely many 3-connected graphs. Moreover, the distribution of values of average genus is sparse, in the following sense: within any finite real interval, there are at most finitely many different numbers that are values of average genus for 2-connected simplicial graphs or for 3-connected graphs. Thus, there are no limit points for the values of average genus of graphs in these classes. The potential applicability of these results to graph isomorphism testing is considered. © 1992.
引用
收藏
页码:83 / 103
页数:21
相关论文
共 18 条
[1]  
CHEN J, 1990, LINEARLY SYNTHESIZIN
[2]  
CHEN J, IN PRESS J COMBIN B
[3]  
CHEN J, 1991, LOWER BOUNDS AVERAGE
[4]  
CHEN JSC, 1990, THESIS COLUMBIA U
[5]   GENUS DISTRIBUTIONS FOR 2 CLASSES OF GRAPHS [J].
FURST, ML ;
GROSS, JL ;
STATMAN, R .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (01) :22-36
[6]   HIERARCHY FOR IMBEDDING-DISTRIBUTION INVARIANTS OF A GRAPH [J].
GROSS, JL ;
FURST, ML .
JOURNAL OF GRAPH THEORY, 1987, 11 (02) :205-220
[7]   GENUS DISTRIBUTIONS FOR BOUQUETS OF CIRCLES [J].
GROSS, JL ;
ROBBINS, DP ;
TUCKER, TW .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 47 (03) :292-306
[8]  
GROSS JL, 1989, STRATIFIED GRAPHS
[9]  
Gross JL., 1987, TOPOLOGICAL GRAPH TH
[10]  
GROSS JL, IN PRESS GRAPHS COMB