Journal of South China University of Technology (Natural Science Edition) ›› 2005, Vol. 33 ›› Issue (7): 101-104.

Previous Articles    

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

Chen Xiao-gen  Peng Hong   

  1. College of Computer Science and Engineering,South China Univ,of Tech.,Guangzhou 510640,Guangdong,China
  • Received:2004-10-13 Online:2005-07-25 Published:2005-07-25
  • Contact: Chen Xiao—gen(bom in 1964)，male，lecturer，master candidate in—service，now works at Zhanjiang Normal University，mainly researches Oil graph theory and computa—tional science E-mail:oamc@ 163.com
  • About author:Chen Xiao—gen(bom in 1964)，male，lecturer，master candidate in—service，now works at Zhanjiang Normal University，mainly researches Oil graph theory and computa—tional science
  • Supported by:

    Suppo rted by the National Natural Science Foundation of China(10261003)，the Key Technologies R&D Program of Guangdong Province(A10210200)and the Key Technologies R&D Program of Guangzhou(2004Z一130091)

PDF

426

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 ν ,there is a walk oflength P from u to v.Let Pn(d) be the set ofall primitive digraphs oforder 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.

Key words: Boolean matrix, common consequent, primitive digraph