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

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

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

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

竞赛图的广义本原指数及其极图

证明了n(n≥7)阶本原竞赛图D的第1个广义本原指数expD(1)＝3,并给出了第k(1≤k≤n)个广义本原指数expD(k)的最大值和最小值及广义指数达到最大值和最小值的极图刻画.     

重上广义指数达到最大值的竞赛图

给出指数达到第k个重上广义本原指数集E^(n,k)中最大值的n(n≥7)阶本原竞赛图极图的完全刻画.     

重上广义指数达到最大值的竞赛图

给出指数达到第k个重上广义本原指数集E(n,k)中最大值的n(n≥7)阶本原竞赛图极图的完全刻画.     

若干本原有向图类其广义本原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-指数的若干上界.     

含有环的单双向间隔的双色有向圈的本原指数

一个双色有向图D(A,B)是本原的,如果存在非负整数h和k,且h+k＞0,使得D(A,B)中的母一对顶点(i,j)都存在从i到j的(h,k)途径,且称h+k的最小值为D(A,B)的本原指数.考虑一类特殊的双色有向图,它的未着色图有n个顶点,包含有一个n-圈,n-1/2个2-圈和n个环,给出了本原条件和指数上界.     

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

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

一类本原有向图的m-competition指数及广义scrambling指数

根据图论、数论和集合的相关知识,对本原图中任一点经过k长途径所到达点的集合进行分析,结合广义competition指数和广义scrambling指数的定义,研究了一类特殊本原有向图(含有2个s-1圈和s个s圈)。得到了这一类本原有向图的m-competition指数以及广义scrambling指数。     

一类双色有向图的本原指数

一个双色有向图D是本原的,如果存在非负整数h和k,h+k>0,使得D的每对顶点(i,j),都存在从i到j的(h,k)-途径.对所有的h和k,h+k的最小值定义为双色有向图D的本原指数.给出了一类双色有向图的本原指数集,并对极图进行了刻化.     

单圈图Merrifield-Simmons指标的第五大值

图G的Merrifield-Simmons指标是指图G的独立集的个数,其中包括空集.文献[3]得到n阶单圈图中具有最大、次大、最小的Merrifield-Simmons指标的图类,以及讨论了当圈长为k时具有最大Merrifield-Simmons指标的图.文献[4,5,9]给出了圈长为k的n阶单圈图的第二大,第三大和第四大Merrifield-Simmons指标及对应的图.文献[10]给出了圈长为3的9阶单圈的Merrifield-Simmons指标的第五大值及对应的图,本文得到圈长为k的n阶单圈图的第五大Merrifield-Simmons指标及对应的图.     

泛圈图的一个新的充分条件

设G是一个阶为n的2－连通简单图,αv表示G中包含点v的最大独立集的点数,对任意uv不属于E,设Tuv=V\(N(u)∪N（v)),αuv=min{αu,αv}。本文证明了：如果对于任一对不相邻点u,v,｜N（u)∩N(v)｜≥min{αuv-1,｜Tuv｜},则除了一些特殊图外,对于G的任一点x和任意整数k(4≤k≤n),G包含长度为k县包含点x的圈。     

恰有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-[d/2]≤L(n,d,k)≤n-1,1≤d≤n．     

正则图的最大-团横贯数与减最大-团横贯数

本文首先得到了阶数为n、团数为k的连通k-正则图的最大-团横贯数的上界n/k以及n阶连通无爪3-正则图的最大-团横贯数的下界n/4,并对达到这些界的极值图进行了刻画。然后对阶数为n、团数为ω（G）的任意图G 的减最大-团横贯数给出了一个紧的下界1＋ω（G）-n,同时对阶数为n、团数为k的连通k-正则图的减最大-团横贯数呈现了一个上界n/k,并刻画了达到这个上界的极值图。     

图的代数连通度及其点连通度

G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.     

循环图中部分图类的导出匹配可扩性

如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±k(mod2n)的i和j,均有xixj∈E(G,)则称其为步长为1和k的循环图,记为C2n(1,k.)通过详细讨论循环图的导出匹配可扩性,具体给出了循环图中的部分图类的导出匹配可扩性。     

对称群Sn（n≤15）的一个新刻画

本文首先通过计算给出了对称群Sn（n≤15）的阶｜Sn｜,最高阶元的阶k1（Sn）,次高阶元的阶k2（Sn）及第三高阶元的阶k3（Sn）。然后利用有限单群分类定理证明了Sn（n=1,2,…,9,11,13,14）可由｜Sn｜和k1（Sn）刻画,即有限群G同构于Sn当且仅当｜G｜=｜Sn｜且k1（G）=k1（Sn）。最后对Sn（n=10,12,15）证明了它们可由｜Sn｜和k1（Sn）,k2（Sn）及k3（Sn）刻画,即G 同构于Sn当且仅当｜G｜=｜Sn｜且k1（G）=k1（Sn）,k2（G）=k2（Sn）及k3（G）=k3（Sn）。     

（a，b，k）-临界图的两个充分条件

设G是一个n阶图，1≤a相似文献   

强连通图的二阶指数集

设Ｄ为ｎ阶强连通图，Ａ（Ｄ）为Ｄ的邻接矩阵，则以Ａ（Ｄ）＋Ａ~２（Ｄ）为本原矩阵，其指数称为Ｄ的二阶指数，ｎ阶强连通图的二阶指数集Ｓ（２，ｎ）＝｛１，２，…，ｎ－１｝。