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

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

作　　者：陈小亘[1] 彭宏[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510640

出　　处：《华南理工大学学报（自然科学版）》2005年第7期101-104,共4页Journal of South China University of Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(10261003);广东省科技攻关项目(A10210200);广州市科技攻关项目(2004Z-D0091)~~

摘　　要：如果存在正整数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.

关 键 词：布尔矩阵 公共后继 本原有向图 

分 类 号：O157.5[理学—数学]