| 摘 要： | 一个图 G 称为是一个(l,d)——稳定图(关于边的),如果对于 G 的边集 E(G)的任意一个子集 E,只要满足 E 中的边数≤l-1,都有图 V-E 的直径 d(V-E)≤d。(这里 l,d 都是正整数)。如果更有G 的直径 d(G)=d,则称 G 为 l 直径稳定图。一个图 G 的边直径稳定度(line-persistence)ρ_1(G)是为了要使得在 G 中去掉一些边后所得到的图 G′的直径 d(G′)>d(G)或者使 G′不连通所必须去掉的最少边数。(l,d)——稳定图和 l 直径稳定图的概念是首先由 J.Hartman 和 I.Rubin 于1956年在[1]中提出的。直径稳定度的概念是由 F.T.Boesch;F.Harary 和 J.A.Kabell 于1981年在[2]中首先提出的。本文对直径稳定图和边直径稳定度作了进一步的考察,得到了一些关于直径稳定图的结论,并初步讨论了直径稳定图和边直径稳定度之间的关系,最后,通过一个引理和一个推论给出了几个 l 直径稳定图族,从而解决了 Hartman 和 Rubin 在[1]中提出的两个问题,同时所给出的图族证明了 Boesch;Harary 和 Kabell 在[2]中所给出的一个关于边直径稳定度的“定理”是不正确的。(注:此“定理”有两种“等价”的叙述方法,本文所给出的图可作为这两种叙述的反例。)
|
