正则图的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等人的结果.     

一类强定向的最小平均距离

用σ_G(v)表示图G中顶点v与G中所有顶点间的距离之和.利用σ_G(v)指标得到了含有割点的2-边连通图G的强定向的最小平均距离的若干下界.     

若干图的倍图的邻点可区别边(全)染色

设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ’as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。     

定向图的斜邻接矩阵的积和多项式（英文）

设G~σ为简单图G的一个定向.介绍了定向图G~σ的积和多项式,得到了G~σ的积和多项式根据图的结构表示的系数公式,证明了一个图G的所有定向图有相同的积和多项式当且仅当G没有偶圈.对定向图G~σ的积和多项式的根也进行了研究.     

基于圈收缩的图的(Sum-)Balaban指标

连通图G的Balaban指标(也叫J指标)的定义是■连通图G的Sum-Balaban指标定义为■其中m,n分别是图G的边数和点数,σ_G(u)表示G中从顶点u到其它各个顶点的距离之和. Balaban指标和Sum-Balaban指标被广泛应用于QSAR和QSPR的研究.证明了:经过圈收缩后,一类单圈图的Balaban指标和Sum-Balaban指标是增大的.观察Balaban指标和Sum-Balaban指标在圈收缩操作中的变化规律,对这两类拓扑指标提出了一种新的比较方法.     

Δ(G)=2的图的孪生强边染色

设σ是一个阶至少为3的简单连通图G的k-正常边染色,其中颜色集合为{0,1,2,…,k-1}.若对任意距离不超过2的两条边e,,存在σ(e)≠σ(),则称σ为G的强边染色.若图G的强边染色σ能够诱导一个G的2-距离点染色,则称σ是G的孪生强边染色.最少的颜色数为G的孪生强边色数,记为■_(s,t)(G).通过研究简单连通图的孪生强边染色,得到了相应的染色数.     

单圈图Merrifield-Simmons指标的第四大值

得到了圈长为k的n阶单圈图的Merrifield-Simmons指标σ(G)的第四大值及对应的图.当k=3时,σ(G)第四大值为9·2n-5十2(n≥7),相应的第四大极值图为Sn-5,p2,c3;当4≤k≤7,n-k≥4时,σ(G)第四大值为2n-k-2(8Fk+1+4Fk-2+Fk-3相应的第四大极值图为Qn-K-2,v3.2,ck;当k=8,9时,σ(G)第四大值分别为58·2n-9+23和94·2n-10+37,相应的第四大极值图为Qn-k-1,v4,ck;当k=10,11时,σ(G)第四大值分别为153·2n-11+59和248·2n-12+95,相应的第四大极值图为Qn-k-1,v6,ck;当12≤k≤n时,σ(G)第四大值为2n-k-1(10Fk-5+8Fk-3)十6Fk-55Fk-5,相应的第四大极值图为Qn-k-1,v7,ck.     

斜秩等于围长的定向图的刻画

设G^σ是定向图,S(G^σ)是其斜邻接矩阵.图G^σ的斜秩sr(G^σ)定义为其斜邻接矩阵的秩.图G^σ的围长,记为g(G),定义为其基础图G中最短圈的长度.刻画了斜秩等于围长的定向双圈图,定向三圈图进而推广至所有定向含圈图.     

具有最大Merrifield-Simmons指标的M_n~k图

一个图的Merrifield-Simmons指标σ(G)定义为图G的所有的点独立集数目之和.该文把有n个顶点的满载单圈图固定k(k≥l,l为圈的长)个悬挂点且圈上每个点都至少连一个悬挂点的单圈图记为Mkn图.该文描述了Mkn图的第一大Merrifield-Simmons指标及其极图特征.     

关于自补置换的若干结果

本文用G表示图G的补图,如果G≌G,则称G为自补图(下称S.C.图).若G是一个S.C.图,则把从G到G的同构映射σ叫做G的自补置换(下称S.C.置换).用P(G)表示S.C.图G的全体S.C.置换的集合,用Γ(G)表示图G的自同构群.对于任一σ∈P(G)(G是S.C.图).由[1]知,σ中除长度为1的圈外,所有的圈长都是4的倍数.