恰有d个顶点带环的本原有向图的公共后继的界(英文)

Bound of Common Consequent of Primitive Digraphs with Exact d Vertices Having Loop

如果存在正整数p,使有向图G中任一有序顶点对u和v都有长为p的途径,则有向图G称为本原有向图.设Pn(d)是n(n≥3)阶恰有d个顶点带环的本原有向图的集合,LG(k)是本原有向图G的k-公共后继(k-c.c.),2≤k≤n;又设L(n,d,k)=max{LG(k)G∈Pn(d)},由此得到了k-公共后继的界:n-「d2﹁≤L(n,d,k)≤n-1,1≤d≤n.

A digraph G is said to be primitive if there exists a positive integer p such that for each ordered pair of vertices u and v, there is a walk of length p from u to v. Let Pn(d) be the set of all primitive digraphs of order n (n≥3) with exact d vertices having loops, LG(k) be the k-common consequent (k-c.c.) of primitive digraph G, 2≤k≤n, and L(n,d,k)=max{LG(k)│G∈Pn(d)}. In this paper, the bound of k-common consequent, namely, n-「d2≤L(n,d,k)≤n-1, 1≤d≤n, is obtained.