Minimum Cycle Bases of Outplanar Graphs on the Torus
-
摘要: 研究环面上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:
- outerplanar graphs /
- noncontractible cycle /
- minimum cycle bases
点击查看大图
计量
- 文章访问数: 1359
- HTML全文浏览量: 3
- PDF下载量: 950
- 被引次数: 0