| 恰有d个顶点带环的本原有向图的公共后继的界 |
| |
| 引用本文： | 陈小亘,彭宏. 恰有d个顶点带环的本原有向图的公共后继的界[J]. 华南理工大学学报(自然科学版), 2005, 33(7): 101-104 |
| |
| 作者姓名： | 陈小亘 彭宏 |
| |
| 作者单位： | 华南理工大学,计算机科学与工程学院,广东,广州,510640;华南理工大学,计算机科学与工程学院,广东,广州,510640 |
| |
| 基金项目： | 国家自然科学基金资助项目(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-[d/2]≤L(n，d，k)≤n-1，1≤d≤n．
|
| 关 键 词： | 布尔矩阵 公共后继 本原有向图 |
| 文章编号： | 1000-565X(2005)07-0101-04 |
| 修稿时间： | 2004-10-13 |
Bound of Common Consequent of Primitive Digraphs with Exact d Vertices Having Loop |
| |
| Chen Xiao-gen,Peng Hong. Bound of Common Consequent of Primitive Digraphs with Exact d Vertices Having Loop[J]. Journal of South China University of Technology(Natural Science Edition), 2005, 33(7): 101-104 |
| |
| Authors: | Chen Xiao-gen Peng Hong |
| |
| Abstract: | 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-[d/2]≤L(n,d,k) ≤n-1, 1 ≤d≤n,is obtained. |
| |
| Keywords: | Boolean matrix common consequent primitive digraph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
