几类本原有向图Scrambling指数极图的广义Competition指数

设D为n阶本原有向图,对于D中的每一对顶点x,y,存在正整数m,1≤m≤n,在D中总能找到m个不同的顶点v1,v2,…,vm,使得x和y到vi(1≤i≤m)都存在k长的途径,上述k中的最小者称为D的广义Competition指数(m-Competition指数).广义Competition指数是本原指数和Scrambling指数的推广.采用图论与组合矩阵论的方法,对几类本原有向图Scrambling指数极图的广义Competition指数进行研究,给出了这几类极图的广义Competition指数.

一类非本原有向图第k个顶点指数集

非本原有向图的广义本原指数是本原有向图的广义本原指数的推广,文中主要给出了围长为2的n阶k-本原(非本原)有向图的第k个顶点指数[expD(k)]的最好上界:(1)若n≥7,则 expD(k)≤n2-7n+k+14;(2)若n=3,5,则 expD(k)≤2n+k-6;(3)若n=4,6,则expD(k)≤2n+k-5.并且确定了相应的指数集.

极小强连通本原有向图的本原指数集

本文的主要结果为:(1)当一个n阶极小强连通本原有向图至少含三个不同圈长时,有γ(D)≤[1/2(n^2-6n+14)](当n≥14时)。(2)e(n)≥[1/2(n^2-6n+16)],即从6到[1/2(n^2-6n+14)]的所有正整数都是某个n阶极小强连通本原有向图的本原指数。(3)给出了n阶极小强连通本原有向图的本原指数集NE_n的明确表达式。

本原有向图D_(n,q,s)的scrambling指数

设n,q,s是正整数,满足1≤s<q≤n,g.c.d.(q,s)=1,且q+s≥n+1.定义有向图D n,q,s=(V,E),其中V={1,2,…,n},E={(i,i+1)1≤i≤n-1}∪{(s,1),(n,n-q+1)}.显然,D n,q,s是本原有向图,且是一类重要的极图.运用了数论和图论的方法得到了Dn,q,s的scrambling指数,根据本原有向图D的本原指数exp(D)与scrambling指数k(D)的已知结论,猜想lim n→∞k(D)exp(D)=1/2.

围长为2的本原有向图的最小顶点指数

研究一类本原有向图的顶点指数 ,证明了n(≥ 3)阶围长为 2的本原有向图的最小顶点指数的最大值exp2 (n ,1)是 :若n是奇数 ,则exp2 (n ,1) =2n - 3;若n是偶数 ,则exp2 (n ,1)=2n - 4 .

围长为2的本原有向图的最小顶点指数集

研究一类本原有向图的最小顶点指数集 ,证明了n(≥ 3)阶围长为 2的本原有向图的最小顶点指数集En是 :若n是奇数 ,则En ={ 2 ,3,… ,2n - 3} ;若n是偶数 ,则En={ 2 ,3,… ,2n- 4 } .

一类本原有向图的第k个顶点指数的研究

广义本原指数的上界和相应的指数集的确定是广义本原指数研究的重要问题。给出了围长为2的n阶 本原有向图的第k个顶点指数(expD(k))的上界及相应的指数集。

奇围长为r的中心对称本原有向图的指数集

R^(n,r)表示全体奇围长为r的n阶中心对称本原有向图。本文给出了R^(n,r)中全体奇围长为r的中心对称本原有向图的指数集。

两个本原有向图的广义本原指数

本文研究了两个本原有向图顶点指数和广义重下指数以及广义重上指数

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

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

若干本原有向图类其广义本原r-指数的界

k点r-指数、k点r-同位指数、第k重下r-指数和第k重上r-指数(统称为广义本原r-指数)是基于非记忆通信系统的数学模型所提出的4类有重要意义与应用背景的新指数.利用有向图的模拟、可达集的分析以及Frobenius数其有关性质的运用等方法技巧,该文主要研究了若干重要的本原矩阵(本原有向图)类其广义本原r-指数的上界估值和极矩阵(极图)刻画等问题:分别对w-不可分矩阵,w-几乎可分矩阵其k点r-指数和第k重上r-指数的上界进行了估值,并进一步刻画了完全不可分矩阵和几乎可分矩阵其k点r-指数和第k重上r-指数的上确界和极图;探讨了含多圈结构的本原有向图、含交圈结构的本原有向图其k点r-指数、k点r-同位指数、第k重下r-指数和第k重上r-指数的上界估值等问题,同时也导出了微对称本原矩阵和对称本原矩阵其4类广义本原r-指数的若干上界.

非本原有向图的最大广义指数及极图刻画

研究几类非本原有向图的广义指数，主要结果有：对非本原的k－本原有向图的广义指数给出了最大值及极图刻画；对强连通K－上本原有向图分别在本原和非本原情形下。

具有环的本原有向图的重指数集(英文)

设S1n(k)和S2 n(k)分别表示至少有一个环的n阶本原有向图的第k个下重指数集和第k个上重指数集 ,对 2≤k≤n - 1,证得S1n(k) ={ 1,2 ,… ,n -k} ,S2 n(k) ={ 1,2 ,… ,2n -k - 1} .

围长为2的n阶本原有向图的Lewin指数集

分析了围长为2的n阶本原有向图的l(G)的上界及相应的指数集,并讨论了极端情形.

直径≤d的对称本原有向图的广义本原指数集

给出了含有自环的直径≤d的全体n阶对称本原有向图的第k(1≤k≤n)个广义本原指数的上确界,并证明了这类有向图的第k个广义本原指数集为:当1≤k≤d时,E0d(n,k)=1,2,…,d-1+k,当d+1≤k≤n时,E0(n,k)=1,2,…,2d。

围长为2的本原有向图的广义本原指数

利用图论和数论相结合的方法,给出了围长为2的n阶本原有向图的每一个广义本原指数的最大值的表达式。

围长为r的n阶本原有向图的点指数

研究本原有向图的顶点指数,运用图论与数论方法,得到了n阶围长为r的本原有向图的点指数expD(k)的上界:若rn,且r为素数,D∈Dn,r={D|D为n阶本原有向图且围长为r},则expD(n,k)=rn-2r+k(1≤k≤n);若r|n,且r为素数或素数的幂,D∈Dn,r,则expD(n,1)=rn-3r+2.

对称本原有向图的广义本原指数集

本文证明了全体ｎ阶对称本原有向图的第ｋ个第一类（１≤ｋ＜ｎ－１）、第二类（１≤ｋ≤ｎ－１）和第三类（２≤ｋ≤ｎ－１）广义本原指数的指数集分别是｛１，２，…，ｎ－２＋ｋ｝和｛１，２，…，２（ｎ－ｋ）｝，其中「ａ］表不小于ａ的最小整数，［ｂ］表不大于ｂ的最大整数。

一个特殊本原有向图的Scrambling指数和广义Scrambling指数

研究一个含有5个圈的n阶本原有向图,其中包含2个n-1圈和3个n-2圈.分析了图中每一点通过l长途径所到达顶点的集合及顶点的个数,结合图论与组合论的相关知识,得出该图的Scrambling指数和广义Scrambling指数.

2个特殊本原有向图的Scrambling指数与广义Scrambling指数

考虑2个含有3个圈(其中2个圈的长度相等但不相交)的特殊本原有向图.通过分析图中每一点经过t长途径所到达的点的集合及点的个数,给出了此类图的Scrambling指数和广义Scrambling指数.