Cartesian积图的分解

若图G的边集能划分成两两不相交的若干个子集，使得每个子集都导出相同的子图H，则称G存在H分解。两个图G=（Vi,Ei）（i=1，2）的Cartesian积，记作G1□G2，其顶点集V=V1×V2，边集E={（（u1，u2），（v1，v2））｜u1=v1∈V1,u2v2∈E2或u2=v2∈V2，u1v1∈E1}。本文给出了路和圈的Cartesian积图存在只分解的充要条件。     

正则图Cartesian积的线图的秩

设G是一个顶点为n,度为r的正则图,那么它的边为m=1/2nr.G线图是顶点为m,度为（2r-2）,边为1/2nr（r-1）的正则图,本文研究两个正则图或强正则图的Cartesian积图的线图的秩,得到了许多结果,推广了G．J．Davis,G．S．Domke等人的结论．     

关于一类Ore图的泛圈性

从所周知，ＪＡＢｏｎｄｙ的Ｍｅｔａｌ猜测对Ｏｒｅ图是成立的。本文从一个新的角度，对Ｇ中次数较小的节点所导出的子图的结构进行了分析，得出了一类新的泛圈图。     

有向圈卡氏积图的哈密尔顿圈

讨论两个有向圈Cn与Cm的卡氏积图Cn×Cm的Hamilton性,给出并证明了:Cn×Cm存在有向Hamilton路,但未必存在有向Hamilton圈;当n｜m时,Cn×Cm必存在有向Hamilton圈.     

图的Hamilton性与无符号拉普拉斯距离谱半径

本文利用图及其补图的无符号拉普拉斯距离谱半径分别给出了一个图包含Hamilton路、Hamilton圈以及是Hamilton连通图与泛圈图的充分条件。     

图的Cartesian积结构分析及其Hedetniemi染色猜想

利用Cartesian积等价地表示出极大扩容图的代数结构,对Hedetniemi染色猜想进行了研究.根据极大扩容图的代数结构性质及与原图的关系,证明了简单图的若干次扩容图满足Hedetniemi染色猜想,得到了对Hedetniemi染色猜想成立的无限类图.     

Ore－型子图对图的Hamilton性的影响

设Ｇ＝（Ｖ，Ｅ）为ｎ阶２－连通的１－坚韧图。将Ｇ的节点分类：ｇ＝｛ｖ∈Ｖ｜ｄＧ（ｖ）≥ｎ／２｝而Ｈ＝（Ｇ＼ｇ）。如果Ｈ满足Ｏｒｅ－条件：ｘ，ｙ∈Ｖ（Ｈ），（ｘ，ｙ）∈Ｅ（Ｈ）ｄＨ（ｘ）＋ｄＨ（ｙ）≥｜Ｖ（Ｈ）｜，则有：（ｉ）Ｇ是Ｈａｍｉｌｔｏｎ的；（ｉｉ）若Ｇ不是偶图，则Ｇ至多丢失长为ｎ－１的圈．     

交叉超立方体网络的边泛圈性

作为超立方体Qn的变型，在点数和边数都相同的情况下，交叉超立方体CQn有比超立方体更好的性质．在已获证明的CQn包含所有长度(从4到2^n)的圈的基础上，进一步改进了这一结果，证明了CQn中每条边落在所有长度(从4到2^n)的圈中．     

关于Hamilton图的新的圈结构定理

设G是一个n阶图,若对于每一个k (3≤k≤n),图G都含有k-圈,则称图G为泛圈图.泛圈图是圈理论研究中的重要课题.研究得到了Hamilton圈上两个不相邻的点在圈上的距离是3的泛圈性结果.     

邻集交和边泛圈性质

邻集交和边泛圈性质朱卓宇吴宗玉＊＊（南京动力高等专科学校，南京２１００４２）（南京炮兵学院，南京２１１１３２）本文用Ｇ表示ｎ（≥３）阶简单无向图，用α表示图的独立数，其它概念和术语见文［１，２］．文［３］利用邻集交和独立数α的关系研究图的点泛圈...     

完全多部图和笛卡儿积图的线性点荫度

图的线性点荫度是对它的顶点进行染色所用的最少颜色数,同时使得染同一种颜色的点集所导出的子图,它的每个分支均为路．本文完全确定了完全多部图的线性点荫度,给出了笛卡儿积图的线性点荫度的一个上界,得到了一些特殊图（ 如路,圈和完全图） 的笛卡儿积图的线性点荫度．     

笛卡尔乘积图的邻域完整度

主要研究了一些笛卡尔乘积图Km×Kn、K2×Cn、格子图Pn1×Pn2×…×Pnk及Tori图Cn1×Cn2×…×Cnk的邻域完整度.     

Cayley图的笛卡尔乘积

Cayley图是由有限群导出的一类重要的高对称正则图,被认为是非常合适的互连网络拓扑结构。百笛卡尔乘积则是从小规模的指定网络构造大规模网络的重要构造方法。本文证明了Cayley图的笛卡尔乘积仍是Cayley图。作为实例,指明循环网络、超立方体、广义超立方体、超环面和立方连通圈等都是Cayley图。这样可以借助于代数方法来分析和研究这些网络的性质。     

关于笛卡尔乘积图边容错直径的研究

笛卡尔乘积是从若干特定的小网络构造大网络的有效方法,边容错直径是衡量一个网络可靠性和效用性的重要标准,研究了笛卡尔乘积网络的边容错直径,并且得到了一个相关的结果.对任何t1,t2≥1,若G1,G2分别是t1边连通的和t2边连通的,则它们的笛卡尔乘积图的边容错直径D’t1+t2(G1×G2)≤D’t1(G1)+D’t2(G2)+1.并且,该不等式中的上界是最好的.     

笛卡尔乘积图的限制边连通性

设G是一个极大限制边连通k-正则图,k≥2．论文证明了：如果│G│〉2k且n≥3,那么笛卡尔乘积图Pn×G是超级限制边连通的,除非G包含子图Kk;如果│G│〉k＋1且n≥3,那么Cn×G是超级限制边连通的,除非n=3且G是圈．     

k-连通半无爪图的Hamilton性质

半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k 1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。     

Cartesian积图的最大拉普拉斯特征值

设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))～(1/2))]+((2p-1)～(1/2))+1.     

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

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

关于圈与完全图的笛卡儿积的测地数

对于图G内的任意两点u和v,在u和v之间的最短路称为u-v测地线.I(u,v)表示位于u-v测地线上所有点的集合,对于S V(G),I(S)表示所有I(u,v)的并,这里u,v∈S.如果I(S)=V(G),那么称S是G的测地集;并把测地集的最小基数称为G的测地数,记为g(G).文章主要研究Cn×K3的测地数.