简单连通图的k阶幂图的指数集(英文)

设Ｇ 是一个ｎ 阶简单连通图,ｋ≥２ 是一个整数．Ｇ 的ｋ 阶幂图记作Ｇｋ ,定义为：Ｖ（ Ｇｋ） ＝ Ｖ（ Ｇ） 且对任意ｕ ,ｖ∈Ｖ（ Ｇｋ） （ ｕ≠ｖ） ,（ ｕ ,ｖ） ∈Ｅ（ Ｇｋ） 当且仅当ｄＧ（ ｕ ,ｖ） ≤ｋ ,则对任意的ｋ≥２ ,Ｇｋ 本原．令Ｅ（ｋ,ｎ） ＝ ｛ γ（ Ｇｋ）｜ Ｇ 是ｎ阶简单连通图｝ ,可以得到Ｅ（ｋ ,ｎ） ＝ｄｋ ｋ＋ １ ≤ｄ ≤ｎ － １ ,　　若２ ≤ｋ≤ｎ － ２ ,｛２｝ ,　　　　　　　　　　　　若ｋ≥ｎ － １ ．     

极小强连通有向图的幂敛指数集

设ＲＤ（ｎ，ｉ）为所有ｎ阶恰含ｉ个极小强连通分支的有向图的集合，ＮＲ（ｎ，ｉ）为所有ｎ阶恰含ｉ个极小强连通分支的有向图的幂敛指数数集，本文给出了ｎ阶具有ｉ个极小强连通分支的有向图的幂指数集ＮＲ（ｎ，ｉ）的一个明确表达式。     

用基本集讨论k—连通图的Hamiltohn—连通性

设Ｇ是ｎ阶ｋ－连通图（Ｋ≥３），称Ｇ的独立集Ｓ为一个基本集，如果存在，得得ｄｉｓｔ（ｕ，ｖ）＝２，本文证明了下述结论：如果对Ｇ的任－ｋ－基本集Ｓ有ｍｕｘ，则Ｇ或者是Ｈａｍｉｌｔｏｎ－连通的或者属于两类例外图之一。     

强连通图的二阶指数集

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

基于改进遗传算法的无向加权图的k点连通扩充

加权图的连通扩充问题已被证明是NP完全问题，作者提出一种改进遗传算法来解决无向加权图的k点连通扩充问题，通过改进遗传算法中的交叉和变异操作有效地改善了群体的效果，有助于搜索解空间中新的区域，能以较大概率搜索到全局最优，仿真结果表明，该算法在原来简单遗传算法上做了进一步改善，为解决加权图的扩充问题提供了新的方法。     

无向Kautz图的限制性连通度和限制性容错直径

证明直径为ｌ且最小和最大度分别为３和４的无向Ｋａｕｔｚ图具有限制性连通度４，且其限制性容错直径至多ｌ＋１４。     

路的k阶幂图的连通性研究

设G是连通图,G的k阶幂图G^k是一个与G具有相同顶点集的图,G^k中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k.本文研究了路的幂图P_n^k的点连通度κ(P_n^k)、边连通度λ(P_n^k)和限制边连通度λ₂(P_n^k).得到：当n>k时,κ(P_n^k)=λ(P_n^k)=k;关于限制边连通度：当2≤n≤k+1时λ₂(P_n^k)=2n-4,当n>k+1时,λ₂(P_n^k)=2k-1.     

连通图二次幂图的Hamilton连通性

本文对圈和树的二次幂图的 Hamilton 连通性进行了研究。     

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

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

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

研究一类本原有向图的顶点指数，证明了ｎ（≥３）阶围长为２的本原有向图的最小顶点指数的最大值ｅｘｐ２（ｎ，１）是：若ｎ是奇数，则ｅｘｐ２（ｎ，１）＝２ｎ－３，若ｎ是偶数，则ｅｘｐ２（ｎ，１）＝２ｎ－４。     

一类几乎可约矩阵的本原指数

应用图论方法推导出至少有一对非零对称元但非对称的n阶本原几乎可约矩阵所成的类(SNBn)的数个指数公式,并进一步确定出(SNBn)的本原指数集(S1∪S2∪S3).     

含对称非零元的奇数阶本原矩阵的指标集

本文证明了:当n为奇数时,含对称非零元的n阶本原矩阵类B的指标集E_B的上确界为3n-4;并且E_B={1, 2, …, 3n-4},不存在缺数段;又设N(A)是A中含正元的个数,则A是含最少正元的n阶本原矩阵的充要条件是A同构于定理6中的A.     

判定k-点连通图与k-边连通图极小性的定理

主要研究了判定ｋ－点连通图是极小的充要条件和ｋ－边连通图是极小的必要条件。     

无向简单图P─中心的求法

本文提出一种方法──把减边法与矩阵法结合起来，可较简便地寻求无向简单图Ｐ－中心。     

迹为零的对称本原矩阵的指数集

本文证明了全体n阶迹为零的对称本原矩阵的指数集：是{2，3，4，…，2n-4}\S，其中S是[n-2，2n-4]中的所有奇数。