Maximum genus and connectivity

被引：22

作者：

Chen, JE

Archdeacon, D

Gross, JL

机构：

[1] TEXAS A&M UNIV, DEPT COMP SCI, COLLEGE STN, TX 77843 USA

[2] UNIV VERMONT, DEPT MATH & STAT, BURLINGTON, VT 05405 USA

[3] COLUMBIA UNIV, DEPT COMP SCI, NEW YORK, NY 10027 USA

来源：

DISCRETE MATHEMATICS | 1996年 / 149卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0012-365X(94)00336-H

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is shown that [beta(G)/3] is the tight lower bound on the maximum genus gamma(M)(G) of 2-edge-connected simplicial graphs, where beta(G) is the cycle rank of the graph G. Also, a systematic method is developed to construct 3-vertex-connected simplicial graphs G satisfying the equality gamma(M)(G) = [beta(G)/3]. These two results combine with previously known results to yield a complete picture of the tight lower bounds on the maximum genus of simplicial graphs.

引用

页码：19 / 29

页数：11

共 15 条

[1]

BOUCHET A, 1976, ORS C PROBL COMB THE, P57

[2] KURATOWSKI-TYPE THEOREMS FOR AVERAGE GENUS [J].