华东师范大学学报(自然科学版) ›› 2006, Vol. 2006 ›› Issue (5): 72-75.

• 数学 统计学 • 上一篇    下一篇

环面上外可平面图的最小圈基

徐 梅1,2 任 韩2 党 英2   

  1. 1. 淮阴师范学院 数学系, 江苏 淮安 223001; 2.华东师范大学 数学系, 上海 200062
  • 收稿日期:2005-01-04 修回日期:2005-06-22 发布日期:2006-09-25
  • 通讯作者: 任 韩

Minimum Cycle Bases of Outplanar Graphs on the Torus(Chinese)

XU Mei1, 2, REN Han2, DANG Ying2   

  1. 1. Department of Mathematics, Huaiyin Teachers College, Huaian Jiangsu 223001, China; 2. Department of Mathematics, East China Normal University, Shanghai 200062, China
  • Received:2005-01-04 Revised:2005-06-22 Published:2006-09-25
  • Contact: REN Han

摘要： 研究环面上2-连通外可平面图G在嵌入∏的面宽fw(G)≧ 2时的圈基理论; 给出在面宽fw(G)≧ 2和边宽ew(G)>m,m=max{li |1≦i≦f}时外可平面图G的最小圈基的结构,其中f记为∏的除Hamilton圈外的面迹数l1...lf为∏的对应面迹的长;并证明了G的最小圈基与其不同伦的两条长度之和最短的不可收缩圈之间存在一一对应.

关键词: 外可平面图, 不可收缩圈, 最小圈基, 外可平面图, 不可收缩圈, 最小圈基

Abstract: This paper investigated the cycle base structures of 2-connected outerplanar graphs on the torus and proved that there is a one-to-one correspondence between the minimal cycle base and two nonhomotopic noncontractible cycles with the shortest total length when $fw(G)≧ 2 and ew(G)>m,m=max{li |1≦i≦f}(l1...lf denote the length of all the non-Hamilton facial walks of G).

Key words: noncontractible cycle, minimum cycle bases, outerplanar graphs, noncontractible cycle, minimum cycle bases

中图分类号: