Given a graph on n vertices with m edges, each of unit resistance, how small can the average resistance between pairs of vertices be? There are two very plausible extremal constructions -- graphs like a star, and graphs which are close to regular -- with the transition between them occuring when the average degree is 3. However, one of our main aims in this paper is to show that there are significantly better constructions for a range of average degree including average degree near 3. A key idea is to link this question to a analogous question about rooted graphs -- namely `which rooted graph minimises the average resistance to the root?'. The rooted case is much simpler to analyse than the unrooted, and one of the main results of this paper is that the two cases are asymptotically equivalent.
翻译：以圆边缘的圆顶图显示,每个单位的抵抗力,两面脊椎的平均抵抗力有多大?有两种非常合理的极端构造 -- -- 像恒星那样的图表,和接近常规的图表 -- -- 当平均程度为3时,它们之间会发生转变。然而,我们本文件的主要目标之一是显示,平均程度的构造要好得多,包括平均程度接近3;一个关键的想法是将这一问题与一个有关根底图的类似问题联系起来,即“根底图能尽量减少对根部的平均抵抗力?” 。根底图比不扎根的要简单得多,而本文的主要结果之一是,这两个案例在性质上是相同的。
相关内容
微信扫码咨询专知VIP会员