期刊论文

Lower Bounds on Maximum Genus of a Connected Graph

中文

交通科学与工程

1674-599X

2000

16

1

11-14

10.3969/j.issn.1674-599X.2000.01.003

本校为第一机构

一个连通图G的最大亏格γM（G）主要由它的Betti亏数 ξ（G）确定。利用匹配数、支配数和围长给出了Betti亏数的两个上界 ,从而也给出了最大亏格的两个下界 ;同时 ,这两个界均是可达的。

It is known that the maximum genus of a graph is mainly determined by its Betti deficiency ξ(G) . In this paper we establish two upper bounds on the Betti deficiency in terms of the matching number and the dominating number as well as the girth of a graph, and thus give two lower bounds on the maximum genus. Meantime we show...