浏览全部资源
扫码关注微信
新疆大学数学系,
Published:1989
移动端阅览
[1]李学良.变换图τ_2(G)连通度[J].新疆大学学报(自然科学版),1989(02):8-16.
李学良. 变换图τ2(G)连通度[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 1989, (2).
[1]李学良.变换图τ_2(G)连通度[J].新疆大学学报(自然科学版),1989(02):8-16. DOI:
李学良. 变换图τ2(G)连通度[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 1989, (2). DOI:
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))={(E1
E2
E3)|E1
E2 are two spanning trees of G and E1
E3 forms a partition of E (G)}.E(τ2(G))={(E1 E2
E3)(F1
F2
F3)|(E1
E3)
(F1
F3)∈V(τ2(G))and sum from i=1 to 3 (|Ei-Fi|=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)
Si(e)={(E1
E3)|e∈Ei and (E1
E3)∈V(τ2(G))}
then if Si(e)(?)φ for i=1
2
3
the induced sudgraph ofSi(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).
0
Views
11
下载量
CSCD
Publicity Resources
Related Articles
Related Author
Related Institution