上本原对称有向图上广义指数的极图

THE EXTREMAL DIGRAPHS OF THE kTH UPPER GENERALIZED EXPONENT FOR k-UPPER PRIMITIVE SYMMETRIC DIGRAPHS

设D是n阶有向图(允许有环但不允许有重复弧),X(?)V(D),集指数exp_D(X)是这样的最小正整数p,使得对D中每个点v,存在从X的至少一个点到v的长为p的途径.若这样的正整数p不存在,则定义exp_D(X)=∞.D的第k重上广义指数F(D,k): =max{exp_D(X)|X(?)V(D),|X|=k},1≤k≤n.如果F(D,k)<∞,则称D是k-上本原的.本文完全刻划了k-上本原对称有向图的第k重上广义指数的极图.

Let D be a digraph （loops are permitted but no multiple arcs） of order n, and let X lohtarn V（D）. The set exponent exPD（X） is defined to be the smallest positive integer p such that for each vertex v of D, there exists a walk of length p from at least one vertex in X to v. If no such p exists, then we define exPD（X） = ∞. Let 1 ≤ k ≤ n. Then F（D, k） ： = max{exPD（X）｜ X belong to V（D）, ｜X｜ = k} is called the kth upper generalized exponent of D. D is said to be k-upper primitive if F（D, k） 〈 ∞. The k-upper primitive symmetric digraph of order n whose kth upper generalized exponents achieve the maximum value is completely characterized.