期刊文献+

变换图τ_2(G)连通度

Connectivity of Transformation Graph τ_2(G)
下载PDF
导出
摘要 M.Farber 等在[2]中引入了“边不交的生成树对”的变换图τ_2(G)的定义,证明了它是连通的.本文讨论了τ_2(G)的连通度,得到了一个下界.特别地,对于2-补树图,即恰含有两个边不交的生成树的图,本文先给出了一种递归方法去构造全体2-补树图,然后证明了2-补树图 G 的τ_2(G)的连通度≥|V(G)|-1,井给出了例子,说明这一下界是最佳可能的. M.Farber et al introduced the concept of graph τ_2(G).Let G be a graphwithout Loops,which may have multiple edges,and contain two spanning treeswith no edge in common,then τ_2(G) is defined as follows.V(τ_2(G))={(E_1,E_2,E_3)|E_1,E_2 are two spanning trees of G and E_1,E_2,E_3 forms a partition of E (G)}.E(τ_2(G))={(E_1 E_2,E_3)(F_1,F_2,F_3)|(E_1,E_2,E_3),(F_1,F_2,F_3)∈V(τ_2(G))and sum from i=1 to 3 (|E_i-F_i|=2)}.They discussed the connectedness of this kind of graphs.Now,the followingmain results are obtained.1.It gives a method to construct all of the graphs which contain exactly twoedge-disjiont spanning trees,called 2-complement tree graphs.2.τ_2 (G) has perfect matching.3.Let e∈E(G),S_i(e)={(E_1,E_2,E_3)|e∈E_i and (E_1,E_2,E_3)∈V(τ_2(G))},then if S_i(e)(?)φ for i=1,2,3,the induced sudgraph ofS_i(e)inτ_2(G) is connected.4.Let|V(G)|=n,|E(G)|=m,α=m-2(n-1),then(i) if α=0,the connectivity of τ_2(G) K(τ_2 G)))≥n-1.(ii) if α≥1,the connectivity of τ_2(G),K(τ_2(G))≥2α.In addition,examplesare given to show that the lower bound in (i) is best possible.Meanwhile,other results are also obtained,which may be useful for the detail-ed study of τ_2(G).
作者 李学良
机构地区 新疆大学数学系
出处 《新疆大学学报(自然科学版)》 CAS 1989年第2期8-16,共9页 Journal of Xinjiang University(Natural Science Edition)
关键词 变换图 连通度 边不交生成权 edge-disjoint spanning trees transformation graph connectivity 2-complemet tree graph
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部