English

运筹学学报

• 运筹学 • 上一篇    

联图的圈基

吕雪征1  魏二玲1,*   宋宏业2   

  1. 1. 中国人民大学数学学院, 北京 100872; 2. 北京第二外国语学院通识教育学院, 北京 100024
  • 收稿日期:2017-11-01 出版日期:2018-12-15 发布日期:2018-12-15
  • 通讯作者: 魏二玲 E-mail: werling@ruc.edu.cn
  • 基金资助:

    国家自然科学基金(No. 11401576)

The basis number of join graphs

LV Xuezheng1  WEI Erling1,*   SONG Hongye2   

  1. 1. School of Mathematics, Renmin University of China, Beijing 100872, China; 2. School of General Education, Beijing International Studies University, Beijing 100024, China
  • Received:2017-11-01 Online:2018-12-15 Published:2018-12-15

PDF

99

摘要：

MacLane于1937年给出了圈基方面的重要定理: 图G是平面图, 当且仅当图G有2-重基. 连通图G_1和G_2的联图G_1\vee G_2指的是在它们的不交并G_1\bigcup G_2上添加边集(u,v)|u\in V(G_1), v\in V(G_2). 对G_1和G_2的联图G_1\vee G_2的圈基重数进行了研究, 得到了一个上界, 改进了Zare的结果. 并在此基础之上, 进一步得到特殊联图C_m\vee C_n的圈基重数的一个上界.

关键词: 联图, 圈空间, 基

Abstract:

In 1937 MacLane gave the important theory on cycle basis: gaph G is planar if and only if G  has a 2-basis. The join G = G_1\vee G_2 of graphs G_1 and G_2 is obtained from  G_1\bigcup G_2 by adding all the edges in {(u,v)|u\in V(G_1), v\in V(G_2)}. In this paper we investigate the  basis number of G = G_1\vee G_2 and obtain an upper bound which improves the bound given by Zare. Based on this, a better bound of C_m \vee C_n is derived too.

Key words: join of graph, cycle space, basis