关于图运算的测地数

对于图G(或有向图D)内的任意两点u和v,u-v测地线是指在u和v之间(或从u到v)的最短路.I(u;v)表示位于u-v测地线上所有点的集合,对于SV(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S.G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数.G的下测地数g-(G)=min狖g(D):D是G的定向图狚,G的上测地数g+(G)=max狖g(D):D是G的定向图狚.对于两个图G和H,u∈V(G)和v∈V(H),在u和v之间加一条边,然后再收缩这条边uv所得的图,记为GuHv.本文主要研究图GuHv的测地数和上(下)测地数.     

几乎2-强二部竞赛图及其得分序列

设Tm,n=(X,Y,E)是一个m×n二部竞赛图,且s(v)表示v在Tm,n中的得分.对于u∈Y,记L(u)={v∈V(Tm,n)|u→v且s(v)=n-1}和J(u)={v∈V(Tm,n)|v→u且s(v)=1}.对于v∈X,L(v)和J(v)的定义是类似的.一个强的二部竞赛图Tm,n称为是几乎2-强的,如果对于每一个x∈V(Tm,n),Tm,n-x-L(x)-J(x)是强的.刻划了蕴含几乎2-强二部得分序列的特征.此结论包含了蕴含2-强二部得分序列的特征.     

完全多部图的符号罗马控制数

设图G=(V,E)是一个简单无向图,若实值函数f:V→{-1,1,2}满足以下两个条件:(i)对于任意v∈V,均有∑_(u∈N[v])f(u)≥1成立;(ii)任意v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V,满足f(u)=2,则称该函数为图G的符号罗马控制函数.定义图的符号罗马控制数为γSR(G)=min{f(V)f是图G的符号罗马控制函数}.通过对完全多部图中的顶点数进行分类,给出了当k≥3时,完全多部图K(n_1,…,n_i,…,n_k)的符号罗马控制数的准确值.     

泛圈图的一个充分条件

本文证明了:如果G是n(≥9)阶2连通无爪图,且G的每个导出子图Z_1,满足当u,v∈V(G)d_(z_1)(u,v)=2时有|N(u)UN(v)|≥n-3,则G是泛圈图或圈.其中Z_1≌(K_2UK_1)VK_1.     

无爪图的泛连通性

证明了如果G是3连通无爪图,且G的每个导出子图A、子图T都满足φ（α、α2）,则G是泛连通图（当u、v∈V（G）,d(u,v)=1时;G中可能不存在（u,v）-k路,k=2,3,4除外）。     

图的均匀染色问题的神经网络模型

对图G（V,E）,若一正常k-染色f使得││f[i]-│f[j]││≤1（i,j=1,2,…,k),其中f[i]={v│v∈V（G）且f(v)=i},f(v)表示顶点v的色,则称f为G（V,E）的k－均匀染色。图的均匀染色问题就是要确定使图G（V,E）具有k-均匀染色的最小的k。建立了图的均匀染色问题的神经网络模型算法。     

正则竞赛图的有向生成三角形

2008年N.Lichiardopol在离散数学-竞赛图中经过给定0,1,2个公共顶点的圈.一文中提出以下公开问题:阶为2n+1的正则竞赛图T,对于任意的x∈V(T)是否存在n个有向三角形Ti使得V(Ti)∩V(Tj)=x(1≤i≤j≤n).文章证明了对于阶数为5,7,9的正则竞赛图,该问题答案是肯定的.     

多部竞赛图的点泛圈性

把c-部完全图的每条边任意加上一个方向后得到的定向图称为c-部竞赛图,设T为c-部竞赛图,定义ig(T)=maxx,y∈VCT│d^ (x)-d^-(y)│。给出了c－部竞赛图具有点泛圈性的一个充分条件,即：设T为c－部竞赛图（c≥13),V1,V2,…Vc为T的各分部。如果│V1│≤│V2│≤…≤│Vc│≤│V1│ 1并且ig(T)≤1,那么T具有点泛圈性。     

笛卡尔积图K2,5×Pn的交叉数

两个图G1和G2的笛卡尔积图G1×G2定义为如下的图:V(G1×G2)=V(G1)×V(G2),E(G1×G2)＝﹛(u1,u2)(v1,v2)︱u1=v1且u2v2∈E(G2),或者u2=v2且u1v1∈E(G1)﹜.确定了笛卡尔积图K(2,5)×P(n)的交叉数为8n.     

若干图的Mycielskian图的边色数

对图G(V,E),μ(G)称为G的Mycielskian图,若V(μ(G))=V(G)∪{v′|v∈V(G)}∪{w}且w V(G),而E(μ(G))=E(G)∪{uv′|uv∈E(G)}∪{wv′}.研究了路、圈、扇、轮图的Mycielskian图的边色数.     

一类非负矩阵对的本原指数

研究了一类特殊的双色有向图,它的未着色图中含有3n-2个顶点,包含一个（2n＋1）-圈和一个n-圈的图,给出了本原条件和指数的上、下界,并对极图进行了刻划.     

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

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

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

一个双色有向图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个环,给出了本原条件和指数上界.     

一类双色有向图的本质原指数及极图刻画

一个双色有向图D是本原的,如果存在非负整数h和k,h＋k〉0,使得D的每对顶点（i,j）,都存在从i到j的（h,k）-途径,并称h＋k的最小值为双色有向图D的本原指数.文章给出了一类双色有向图的本原指数集,并对其极图进行刻画.     

一类双色有向图的指数

研究一类特殊的本原双色有向图,其未着色的有向图有2n 1个顶点,包含一个(2n 1)-圈和一个(n 1)-圈.给出了这个双色有向图的指数的边界和极图的刻划.     

奇围长为r的对称图的指数集

令E_(r,n) 表示夸围长为r的n阶对称图的指数集。本文证明了:E_(1,n)={1,2,…,2n-2}\x_1,当3≤r≤n时,E_(r,n)={r一1,r,…,2n-r-1}\x_r 其中x_i为[2[n\2]-i+2,2n-i-1]中的奇数,i=1,r.并刻划了指数为2n-r-1的奇围长为r的对称图的特征。     

一类本原有向图的m-competition指数

设D是一个n阶本原有向图, 对于正整数m及n(1≤m≤n), 定义本原有向图D的m competition指数为最小正整数k, 满足对于任意一对顶点x和y, 在D中都存在m个不同的顶点v1,v2,…,vm,使得xkvi且ykvi(i=1,2,…,m).文中讨论了一个含有两个n-2圈和一个n-3圈的n阶本原有向图D。由D的结构得到本原有向图Dn-2和Dn-3, 再根据m-competition指数的定义, 得到这个本原有向图D的m-competition指数。     

弱距离正则有向图的构作

设Γ是围长g≠2的强连通有向图,C*r是长为r的无向圈.构作了从Γ到C*r的字典式积图Γ'＝Γ[C*r],给出了Γ'＝Γ[C*r]是弱距离正则有向图的充要条件.     

特殊非负矩阵对的指数

文章主要考虑了特殊非负矩阵对的本原指数，其中与该负矩阵对相应的图包含两个圈．我们给出了该本原指数的界并且对其对应双色图的极图进行了刻画．     

一类恰含三个圈的三色有向图的本原指数

一个三色有向图D是本原的,当且仅当存在非负整数h、k和v, 且h+k+v>0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,v)途径, 称h+k+v的最小值为D的本原指数。 本文研究一类特殊的三色有向图,其未着色图恰含一个n-圈、一个(n-1)-圈和一个2-圈, 给出了本原条件和本原指数上界, 并对本原指数上界的极图进行了刻划。