强定向图的k-强距离

摘要

对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界.%For a nonempty vertex set S in a strong digraph D, the strong distance d(S) of S is the minimum size (the number of edges) of a strong subdigraph of D containing the vertices of S. If S contains k vertices, then d(S) is referred to as the k-strong distance of S. For an integer k≥2 and a vertex v of a strong digraph D, the k-strong eccentricity sek(v) of v is the maximum k-strong distance d(S) among all sets S of k vertices in D containing v. The minimum k-strong eccentricity among the vertices of D is the k-strong radius of D sradk(D) and the maximum k-strong eccentricity is the k-strong diameter of D sdiamk(D). In this paper, we will show that for any integers r,d with k+1≤r,d≤n, there exist strong tournaments T′and T″ of order n such that sradk(T′)=r and sdiamk(T″)=d. And we also give an upper bound on the k-strong diameter of strong oriented graphs.