组合星图中一对一容错路由算法

解决了组合星图的一对一容错路由问题.给出了故障节点不超过n-2时,无故障节点s到t的路由算法,证明了算法可以在O(n)内找到一条长度不超过D(Sn,k) 4的路P:s t,其中,D(Sn,k)是Sn,k的直径.运用列举法,推导出组合星图Sn,k中任意点p到固定点Ik的距离公式;并从图论的观点,推导出Sn,k任意2个子图之间的星边数目为(n-2)!/(n-k)!.     

S_n局部补图结构的一点注记

刻画了星图Sn的局部补图σn >(Sn)的结构,以及σn >σnu>(Sn)的结构,并通过对二元秩的计算验证了其正确性.     

星图网络的定向图

主要研究了星图网络Sn的定向图.证明了如下结论:对于非负整数a和b,若存在满足每个顶点的入度或者是a或者是b的一个Sn的定向图,则存在非负整数s和t满足方程s+t=n!和as+bt=(n-1)/2.进一步,对于满足特定条件的非负整数a,b和n,存在Sn的定向图使得每个顶点的入度或者是a或者是b.     

三类组合图的伴随多项式的因式分解及色性

通过研究星图Sn 1的三类组合图的伴随多项式的因式分解,证明了这三种图的补图的色等价图的特征性质.     

K5\e×Sn的交叉数

K5\e×Sn表示将完全图K5删除一条边e所得到的图,Sn表示星图K1,n.证明了一类特殊的图Hn的交叉数为Z(5,n)+2n以及笛卡儿积图K5\e×Sn的交叉数为Z(5,n)+4n.     

分离航天器网络动态连接

不同于地面无线传感网络,分离航天器网络拓扑具有动态、随机特性。首先,基于计算机几何理论如Delaunay Triangulation,Voronoi Diagram建立分离航天器动态拓扑网络。通过分析网络拓扑结构的邻接矩阵中节点间的关系设计邻接矩阵算法得出各网络节点对应的感知半径、通信半径、邻接矩阵,最后得到了基于时空演变的节点间邻居关系的"星图",直观地反应了分离航天器网络节点动态连接的连通性和覆盖度。     

G10×Sn的交叉数

本文证明了五阶图G10与星Sn的笛卡尔积交叉数,填补了Marian Klesc所给出的五阶图与星图的笛卡尔积交叉数表格中的又一个空白.     

两类组合图之并的补图的色等价性

通过研究星图Sn＋1的两类组合图之并的伴随多项式的因式分解，证明了这类并图的补图的色等价性。     

S类组合图的补图的色性分析

通过研究星图Sn＋1的三类组合图的伴随多项式的因式分解，证明了这三种图的补图的色等价图的特征性质。     

两类组合图的伴随多项式因式分解及色性

通过研究星图Sn=1的两类组合图的伴随多项式的因式分解,证明了这两种图的补图的色等价图的特征性质．     

若干联图的星全染色

图G的一个正常全染色如果满足G中任意路长为2的点和边着色均不相同,称为G的星全染色.图的全部k-星全染色中所用最少的颜色数称为图G的星全色数.文章研究了若干联图的星全色数.     

若干笛卡尔积图的星全染色

图G的一个正常全染色如果满足G中任意路长为2的点和边着色均不相同时,称为G的星全染色.图的全部k-星全染色中所用最少的颜色数称为图G的星全色数.得到了路与星、轮、扇的笛卡尔积图的星全色数.     

树的[r，s，t]-着色

通过用树T的导出星K1,△（r）的一个r,s,t]-着色对树T进行点、边着色,证明了树的[r,s,t]-色数等于树中最大导出星的[r,s,t]-色数．     

一些特殊树的对偶带宽

图G的对偶带宽是指图G中相邻两点最小标号差的最大值。确定了一些特殊树的对偶带宽，主要结果如下：(1)如果树T有n个顶点，并且其最大度△(T)不小于[n/2]，那么树T的对偶带宽等于n一△(T)的充要条件为T是双层星且其内星的中心为最大度顶点；(2)完全二叉树T2,k的对偶带宽等于2^k-1；(3)等高单毛虫树Pm,n的对偶带宽为[mn/2]。     

萤火虫图距离矩阵的两个最大特征值和的下界

令n=2r+2t+s+1(r,s≥1,t≥0),Sn-t是一个n-t阶的星,将S_(n-t)中的r对不同的点分别用r条边连接,在另外的t条悬挂边上分别接上一条边,得到的图叫作萤火虫图.令图G是n个点的萤火虫图,主要确定了图G的距离矩阵D(G)=(d_(ij))_(n×n),距离拉普拉斯矩阵L_D(G)与距离无符号拉普拉斯矩阵Q_D(G)的两个最大特征值和的下界.     

几个六阶图与星S_n的笛卡尔积交叉数

分别连结六阶图G1的6个顶点与其它n个顶点,得到一类特殊的图Hn.运用组合方法、归纳思想及反证法证明了Hn的交叉数为Z(6,n)+2「n/2」,并在此基础上证明G1与星K1,n的笛卡尔积的交叉数为Z(6,n)+2「n/2」;另外,证明了含子图S5的其它6个六阶图与星K1,n的笛卡尔积的交叉数都为Z(6,n)+4「n/2」.     

图的k-星着色的Grbner基求解

对于具有n个顶点的简单连通图G,首先证明求解G的k-星着色等价于一个多元多项式方程组在{1,2,…,k}上的求解问题,其次使用Grbner基给出求解该多元多项式方程组的方法,从而得到求G的星色数的一个可行途径,最后通过实例验证了此代数计算方法的有效性.     

pq阶Cayley图的符号星控制数

设G=(V,E)是一个没有孤立顶点的图,如果一个函数f:E→{-1,1},满足f(E(v))≥1,v∈V(G),则称f为图G的一个符号星控制函数.图G的符号星控制数定义为:γss(G)=min{f(E)|f为G的反符号星控制函数},论文确定了pq(2pq,且p、q为互异的素数)阶群Q上Cayley图X(Q,M)的符号星控制数γss(X(Q,M))=(p-1)q+1,M表示群Q的极小生成集.     

一些卡方积图的符号星控制数

设G=(V,E)是一个没有孤立顶点的图,如果一个函数f:E→{+1,-1},对一切v∈V(G)满足∑e∈E(v)f(e)≥1成立,则称f为图G的一个符号星控制函数。图G的符号星控制数定义为γ’ss(G)=min{∑e∈E(v)f(e)∣f为G的符号星控制函数}。在图的符号星控制概念的基础上,确定了两类特殊图的符号星控制数。     

轮和路的广义Mycielski图的星全染色

图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同.图的全部星k-全着色中最小的数k称为它的星全色数.讨论轮和路的广义Mycielski图的星全染色问题,得到不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色.