基于强乘积运算下图的广义和连通度指标上下界

对于图G,令E(G)表示G的边集,令V(G)表示G的点集,d_(G)(v)表示v的度。对于边e=uv,定义广义和连通度指标χ_(α)(e)=(d_(G)(u)+d_(G)(v))^(α),其中α为任一实数。本文先介绍了图的S,R,Q,T四种运算,然后给出了四种运算下的强乘积,并利用最大度最小度确定了其四种图的广义和连通度指标的上下界。

基于字典序乘积下广义和连通度指标的上下界

对于图G,令E(G),d_(G)(v)分别表示G的边集和顶点v的度。对于边e=uv,定义广义和连通度指标χ_(α)(e)=(d_(G)(u)+d_(G)(v))^(α),其中α为任意实数。在对两个简单的连通图G和H做乘积之前,先对其中一个图H进行S,R,Q,T4种运算,运算后的图记为F(H)(其中F∈{S,R,Q,T}),再对图G和F(H)做字典序乘积,给出了基于字典序乘积下图的广义和连通度的指标上下界,并且这些界都是最好的。

双圈图关于和连通度指标的最大值的排序

和连通度指标是指图G的边的权的总和,这里边uν的权等于(d_G(u)+d_G(ν))-1/2,d_G(u)表示点u的度。研究得到了恰好含有一条悬挂路的和连通度指标第一最大及第二最大的双圈图,并对双圈图按照和连通度指数的第三及第四最大值进行排序。