论文部分内容阅读
图G中某一顶点x的覆盖花费CC(x)定义为随机游走从顶点x到G中其余顶点的平均首达时间之和。设Sn^p,q是在圈Cp和圈Cq唯一的公共点上添加n+1-p-q条边得到的双圈图,给出了恰好有2个圈的双圈图中首达时间及覆盖花费与相关图不变量的关系,并通过一些图操作证明了所有恰有2个圈的双圈图中Sn^3,3具有极小值的CC(x),其中x是一个悬挂点。