摘要
一个三色有向图D是本原的,当且仅当存在非负整数h、k和v,且h+k+v>0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,v)-途径,称h+k+v的最小值为D的本原指数。本文研究一类特殊的三色有向图,其未着色图恰含一个n-圈、一个(n-1)-圈和一个2-圈,给出了本原条件和本原指数上界,并对本原指数上界的极图进行了刻划。
A three-colored digraph D is primitive if and only if there exists nonnegative integers h, k and v with h ＋ k ＋ v 〉 0 such that for each pair （i,j） of vertices there exists a （ h, k, v）-walk in D from i to j. The exponent of the primitive three-colored digraph D is the minimum value of h ＋ k ＋ v taken over all such h, k and v. Special three-colored digraphs were studied, whose uncolored digraph consists of one n-cycle, one （ n - 1）-cycle and one 2-cycle. Some primitive conditions and an upper bound on the exponent were given. Further, the characterizations of extremal three-colored digraphs were put forth.
出处
《山东大学学报（理学版）》
CAS
CSCD
北大核心
2008年第1期65-72,共8页
Journal of Shandong University(Natural Science)
基金
国家自然科学基金资助项目(10571163)
山西省自然科学基金资助项目(20041010)
关键词
三色有向图
本原指数
极图刻划
three-colored digraph
primitive exponent
extremal digraph
