两种运算下图的Szeged指标和修正Szeged指标的计算

图G的Szeged指标Sz(G)和修正的Szeged指标Sz*(G)分别定义为Sz(G)=Σuv∈E(G)nunv和Sz*(G)=Σuv∈E(G)(nu+n0/2)(nv+n0/2).这里,对于边uv,n0是指图中到u和v距离相等的点数,nu是指图中距u比距v近的点数,nv类似定义.本文给出了强正则图的联图和合成图的Szeged指标和修正Szeged指标的计算公式.     

一类3-正则图的关联邻点可区别全染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,...,k}的映射,k是自然数,若f满足(1)uv∈E(G),u≠v,f(u)≠f(v);(2)uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)uv∈E(G),C(u)≠C(v);其中C(u)={f(u)}∪{f(uv)|uv∈E(G)};则称f是G的一个关联邻点可区别全染色.给出了一类3-正则重圈图Re(n,m)(m≥2,n≥3且n≡0(mod2))的关联邻点可区别全色数.     

正则图的Balaban指标

连通图的Balaban指标(也叫J指标)的定义是m1J(G)=m-n+2uv∑∈E(G)σG(u)σG(v)其中m,n分别是图G的边数和点数,σG(u)表示在G中从顶点u到其它各个顶点的距离之和.Balaban指标被广泛应用于各种QSAR和QSPR的研究.首先给出连通3-正则图的Balaban指标的一个上界.然后对KNOR M等人介绍的两类3-正则图,分别给出它们的Balaban指标计算公式和上界,改进了KNOR M等人的结果.     

二正则图的和数

设S是自然数集N*的一个有限集.定义在S上的和图G~+(S)是图(S,E),满足uv∈E当且仅当u+v∈S.称一个图G为和图,如果存在一个S,使得G≌G~+(S).对于一个图G,称使得G∪r K_1是和图的最少的孤立点的个数r为G的和数.和图的概念首先是由Harary提出来的,并且他指出除了C_4的和数为3外,所有的圈C_n的和数都是2.本文研究了全部二正则图的和标号问题,证明除了C_4外所有的二正则图的和数都是2.     

图的Laplacian谱半径界的可达性

设G为n阶连通的简单图 ,ρ(G)为图G的邻接谱半径 ,μ(G)表示G的Laplacian谱半径。(d1,d2 ,… ,dn) (其中d1≥d2 ≥…≥dn)为G的顶点度序列 ,令r=max{d(u) +d(v) ｜ (u ,v) ∈E(G) } =d(x) +d(y) ,s=max{d(u) +d(v)｜ (u ,v) ∈E(G) - (x ,y) }。该文证明了μ(G)上下界的可达性 :μ(G) =μ≤ 2 + ρ(LG) ,等式成立当且仅当G是偶图。μ(G)≤ 2 + (r- 2 ) (s- 2 ) ,成立等式当且仅当G为半正则偶图或P4 。μ(G)≥d1+ 1,成立等式当且仅当d1=n- 1。     

(2md+1)-正则图中的2d-因子

设m，d都是正整数且m≥2，G是一个(2md 1)-正则图，证明了若G不含(2m-3)d 4条割边，则G有一个2d-因子，进而说明上述结果是最好的。     

Sm∨Fn的全色数

设G(V,E)是阶数至少是2的简单连通图,k是正整数,若f是从V(G)∪E(G)到{1,2,…,k}的一个映射,使得:对于任意的uv,vw∈E(G),u≠w,有f(uv)≠f(vw);且对于任意的uv∈E(G),u≠v,有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),则称f为G的一个k-全染色(简记成k-TC of G).而χt(G)=min{k|k-TC of G},称为G的全色数.设G和H是点边都不相交的简单图,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G),v∈V(H)},则称G∨H是G与H的联图.给出m 1阶星和n 1阶扇的联图的全色数.     

齿轮图都是调和图

称一个含q条边的简单图G是一个调和图,若存在单射h:v(G)→{0,1,…q-1}使得导出映射h~*:E(G)→{0,1,…,q-1},h~*(uv)≡h(u)+h(v)(modq)是一个双射。这里u,v∈V(G),uv∈E(G)。在轮W_n的轮圈C_n上每两个相邻点之间加入一顶点所得之图称为齿轮图(?)_n。本文将证明,所有齿轮图(?)_n都是调和图。从而回答了[4]中提出了一个open问题。     

局部几乎正则多部竞赛图中的外路

有向图中一点u（一条弧uv）的一条外路指的是从u（uv）开始的一条有向路,如果u控制路的终点当且仅当终点也控制u.一个n-部竞赛图是n-部完全图的一个定向.令V1,V2,…,Vn是n-部有向图D的部集.如果D中存在2条外路P和P使得对于每一个i∈{1,2,…,n}都有Vi∩（V（P）∪V（P））≠Ф,则称P和P是D的一对分量共轭外路.定义D的局部非正则度为il（D）=max｜d＋（x）-d-（x）｜,x∈V（D）,其中d＋（x）和d-（x）分别表示点x的出度和入度.如果il（D）≤1,则D是局部几乎正则的.本文证明了每一个部集具有相等的基数的局部几乎正则多部竞赛图都包含2条长至少为2的分量共轭外路.     

可迹、邻域并和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)＝V(G),E(G*)＝E(G)∪{uv;uv∈E(G),且J(v,v)≠φ},这里J(u,v)＝{w∈N(u)∩N(v)N(w)∪N[u]∪N[v]}.本文利用插点方法,得到k-连通图(k≥1)是可迹的两个新的充分条件.     

仅有三个悬挂点的图的补图的最小特征值

设图G是点集为V(G)＝{v1,v2,…,vn}的简单连通图,则G的邻接矩阵是A(G)＝(aij)n×n,其中若vi和vj相邻,则aij＝1,否则aij＝0.由于A(G)是实对称的,因此可将其特征值设为λ1(G)≥λ2(G)≥…≥λn(G),且A(G)的特征值也称为G的特征值.该文在仅有三个悬挂点的图的所有连通补图中,确定了其最小特征值达到最小值时的唯一图.     

轮形图和扇形图的优美性

设L为简单无向图G的一个顶点标号,若L满足:(1)L为G的顶点集V到{0,1,…,|E|}的一个单射;(2)由L(′e)=|L(u)-L(v)|(其中e=uv)决定的边标号L′是从G的边集E到{0,1,…,|E|}的一个双射,则L称为图G的优美标号.论文研究了轮形图和扇形图的优美性,并给出它们的优美标号.     

一类新图的奇优美性的研究

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足以下两条:(1)L为G的顶点集V到{0,1,…,2 ︱E︱-1}的一个单射;(2)由L′(e)=︳L(u)-L(v)︳(其中e=uv)决定的边标号L′是从G的边集E到{1,3,…,2 ︱E︱-1}的一个双射.本文给出了一类特殊简单图G*的奇优美标号,并给出了相应的标号算法及相关的一些证明.     

关于图的距离无符号拉普拉斯谱半径的下界

若一个连通图G的点集是V(G)＝{v1,v2,…,vn},那么图G的距离矩阵D(G)＝(dij),其中dij表示点vi与vj之间的距离. 令TrG(vi)书版无此符表示点vi到图G中其他所有点的距离之和,Tr(G)表示i行i列位置的元素TrG(vi)的对角矩阵. 图G的距离无符号拉普拉斯矩阵QD(G)＝Tr(G)＋D(G).QD(G)的最大特征值λQ(G)是图G的距离无符号拉普拉斯谱半径.该文确定了给定匹配数的n个点的图的距离无符号拉普拉斯谱半径的下界.     

一类泛连通的无爪图

本文证明了:如果G是3连通的无爪图且G的每个导出子图A,A~(?)都满足ψ(a_1,a_2)则G是泛连通图(除了当u,v∈V(G),d(u,v)=1时,G中可能不存在(u,v)—k路,k∈(2,3,4)以外)     

伞状树的奇强协调性

设G=V,E是一个简单图,若存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足(1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);(2)对任意的e1,e2∈E,若e1≠e2则g(e1)≠g(e2),此处g(e)=f(u)+f(v),e=uv,且{g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇强协调图,f为G的奇强协调标号,讨论了一类树的奇强协调性.     

6-连通图最长圈上的可收缩边

 图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图一些性质的有力工具。设G是一个6-连通图,e∈E（G）,若收缩e后得到的图仍是6-连通的,则称e是G的可收缩边。采用树型结构理论进行分类讨论,得到如下结论：① 如果P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,xi xi+1是一条不可收缩边,且S={xi,xi+1,u1,u2,u3,u4}是其对应的6-点割,则G-S的每一个断片至少包含P上的一个点;② 设P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,且G的任意断片的阶都大于2。如果P上任意顶点xi都满足条件d（xi）≥7或者若d（xi）=6则[V（P）]中无3-圈包含它,那么P上至少包含一条可收缩边。在上述结论的基础上,进一步研究了任意断片阶都大于2的6-连通图中最长圈上的可收缩边的分布情况,得到如下新结果：任意断片阶都大于2的6-连通图最长圈上至少有两条可收缩边。     

无爪图中具有指定长度的路因子

在无爪图G中,设σ2(G)表示不相邻顶点度和的最小值. 令|V(G)|=n=∑ki=1ai,ai6,1ik,并且σ2(G)n+k-1,证明了对于图G中任意的k个顶点v1,v2,…vk, 都存在点不相交的路P1,P2,…Pk，使得对于1ik，都有|V(Pi)|=ai并且vi是路Pi的一个端点.     

点可迁图的限制边连通度

对于度k( ≥ 2 )的点可迁连通图的限制边连通度λ′,已知k≤λ′≤ 2k- 2 ,且λ′的界可以达到 .在此基础上 ,对度为k的点可迁图G进一步给出了满足λ′(G) =k的两个充要条件 .接着 ,对任意的连通图G0 证明了λ′(K2 ×G0 ) =min{2δ (G0 ) ,2λ′(G0 ) ,v(G0 ) }.最后证明了对任意满足 0≤s≤k- 3的整数s,存在度为k的点可迁连通图G满足λ′(G)=k s当且仅当k为奇数或者s为偶数     

仅有三个非负特征值的图

假设图G的点集是V＝,用A(G)＝(aij)n×n来表示图G的邻接矩阵,其中,若vi和vj相邻则aij＝1,否则aij＝0.由于A(G)是实对称的,因此可以将其特征值设为λ1(G)≥λ2(G)≥…≥λn(G). 该文刻画了一部分仅有三个非负特征值的图.