摘要
如果存在正整数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 Pn(d) be the set of all primitive digraphs of order n (n≥3) with exact d vertices having loops, LG(k) be the k-common consequent (k-c.c.) of primitive digraph G, 2≤k≤n, and L(n,d,k)=max{LG(k)│G∈Pn(d)}. In this paper, the bound of k-common consequent, namely, n-「d2≤L(n,d,k)≤n-1, 1≤d≤n, is obtained.
出处
《华南理工大学学报(自然科学版)》
EI
CAS
CSCD
北大核心
2005年第7期101-104,共4页
Journal of South China University of Technology(Natural Science Edition)
基金
国家自然科学基金资助项目(10261003)
广东省科技攻关项目(A10210200)
广州市科技攻关项目(2004Z-D0091)~~
关键词
布尔矩阵
公共后继
本原有向图
Boolean matrix
common consequent
primitive digraph