双星树的Merrifield-Simmons和Hosoya指数序

i(G)表示图G的Merrifield-Simmons指数,定义为图G的独立集个数;m(G,k)表示G的k-匹配数,z(G)表示图G的Hosoya指数,则z(G)是m(G,k)的总和.给出n阶双星图Sp,q的Merrifield-Siimmons指数和Hosoya指数以及关于Merrifield-Simmons指数和Hosoya指数的完全排序.     

棒棒糖图的Merrifield-Simmons和Hosoya指数

i（G）表示图G的Merrifield-Simmons指数,定义为图G的独立点集个数;z（G）表示图G的Hosoya指数,m（G,k）表示G的k-匹配数,则z（G）是所有的m（G,k）的总和（1≤k≤[n/2]）,其中n是G的顶点数．给出n阶棒棒糖图Ln．k的Merrifield-Simmons指数和Hosoya指数以及它关Merrifield—Simmons指数和Hosoya指数的一个排序．     

一类(n,n+2)-图关于Merrifield-Simmons指标和Hosoya指标的排序

Merrifield-Simmons指标和Hosoya指标是化学图论中两个重要的拓扑指标.图G的Merrifield-Simmons指标表示该图中所有独立集的数目,图G的Hosoya指标表示该图中所有匹配的数目.文中研究了一类(n,n+2)图T(k)的Merrifield-Simmons指标和Hosoya指标,并给出了该图类关于这两种拓扑指标的排序.     

Θ(n,g)中关于Hosoya指标和Merrifield-Simmons指标的极值θ-图

对于图G,Hosoya指标和Merrifield-Simmons指标分别定义为图G中所有匹配的和及所有独立集的和.θ-图是通过剖分有公共顶点的3条平行边而得到的图.Θ(n,g)表示围长为g的n阶θ-图的集合.得到Θ(n,g)中Hosoya指标和Merrifield-Simmons指标的最小值、最大值,并刻画了相应的极值...     

单圈图的增强型Zagreb指数的下界

设图G=(V, E)是具有n(n≥3)个顶点、m条边的简单连通图,图G的度序列为{d_1,d_2,...,d_n},定义图G的增强型Zagreb指数(记作AZI)为:■.利用有关不等式的性质,讨论了单圈图的增强型Zagreb指数,得到了该类图的增强型Zagreb指数的几个精确下界.     

关于Hosoya指标和Merrifield-Simmons指标的k色极图

图的Hosoya指标定义为图中包含空边集在内的对集总数.图的Merrifield-Simmons指标定义为图中包含空点集在内的点独立集总数.考虑点数为n的k色连通图的集合Gn,k,证明了Tur n图Tn(k)是Gn,k中Hosoya指标最大且Merrifield-Simmons指标最小的图,还确定了k=2,3时Gn,k中Hosoya指标最小且Merrifield-Simmons指标最大的图.     

若干冠图关于Merrifield-Simmons指标和Hosoya指标的计数

图G的Merrifield-Simmons指标表示该图中所有独立集的数目,图G的Hosoya指标表示该图中所有匹配的数目.文章研究了两类特殊冠图PnoH和CnoH关于Merrifield-Simmons指标和Hosoya指标的计数,得到了更为一般的结果.     

单圈图的Hosoya指数序

设m(G,k)表示图G的k-匹配数,z(G)表示G图的Hosoya指数,它是所有m(G,k)的总和.Hosoya指数是化学图论中一个重要的拓扑指数,通过单圈图的分析给出了Hosoya指数前八小的单圈图.     

具有最大度的图增强型Zagreb指数的上界

设图G=(V,E)是具有顶点n(n≥3)、边m的简单连通图,定义图G的增强型Zagreb指数(简记作AZI)为:AZI=AZI(G)=∑ij∈E(didj/di+dj-2)3,这里{d1,d2,…,dn}表示图G的度序列,最大度记做Δ.利用不等式的有关性质,探讨图的增强型Zagreb指数的上界问题,得到了几个有意义的结...     

一类双圈图的Merrifield-Simmons指标和Hosoya指标序列

一个图的Merrifield-Simmons指标是指这个图的顶点独立集的个数,其中包括空集.一个图的Hosoya指标是指这个图的边独立集的个数,其中包括空集.用代数组合的方法给出了一类双圈图的Merrifield-Simmons指标和Hosoya指标及关于Merrifield-Simmons指标和Hosoya指标的完全排序.     

顶点最大度被限制的图的边转发指数

对于给定的n阶连通图G,一个路由选择R是指G中的n(n-1)条路集,其中每个有序点对都有路集中的一条路连接.图G关于R的边转发指数π(G,R)是R中路经过一条边的最大条数.图G的边转发指数π(G)是G关于任何路由选择R的边转发指数π(G,R)的最小值.符号πΔ,n表示所有顶点数为n,最大度至多为△的图中最小边转发指数.当n≥4p 1,且n()[4p [1/3(2p-1)]-1,6p]时,其中p≥1,确定了πn-2p,n的值.     

具有极小Hosoya指数的共轭树

共轭图即含有完备匹配的图,用τn表示含有n个顶点（n为偶数）的共轭树．z（G）表示图G的Hosoya指数,即图G的所有匹配个数之和．本文用组合数学的知识讨论了矗中具有最小、次小、第三小Hosoya指数的极值共轭树．     

关于二连通图中的最长圈

§1 符号及预备知识本文中提到的图论中最基本的概念,例如点、边、链、圈、子图、主子图等,均按一般图论书中的定义。文中的链(圈)指的是初等链(圈),图指的是简单图。图G的点集记作V(G),边集记作E(G),G中包含的最长圈的长度称为G的周长,记为c(G)。设(?)V(G),(?)V(G),(?)∩(?)=φ,Y是一条起点属于(?)而终点属于(?)的链,且V(Y)中别的点均不属于(?)∪(?),则称Y是一条(?)-(?)链,特别,当链长为1时,称为一条(?)-(?)边。若(?)={A},(?)={B},称Y为A-B链。设u∈V(G)。u在G中的邻域指的是这样的点集{u∈V(G)|uu∈E(G)},记作N(u)。如果Y是G的子图,我们将V(Y)导出的子图记为G(Y)。     

关于 Randic 指数及图的直径

设图G=(V , E)是简单图,其中V是顶点集,E是边集.对G中任意顶点v∈V, dv表示点v的度数.图G的Randic指数也称为图G的连通性指数,定义为R=R(G)=∑uv∈E(1)/(dndv).关于连通图的Randic指数R与直径D有如下猜想:R-D≥2-(n+1)/(2)且(R)/(D)≥(1)/(2)+(2-1)/(n-1),两个等式都成立当且仅当G≌Pn.本文将简化该猜想,并进一步证明当D≤(2(n-1)(3)/(2))/(n-3+2 2)或D≤n-3时,猜想成立     

关于图运算的和连通指标（英文）

设G=(V,E)是一个简单的连通图,V(G)和E(G)分别是图G的顶点集和边集,其中|V(G)|=n,|E(G)|=m.设d_i是点v_i的度数,i=1,2,…,n.Zhou和Trinajasti c′定义了一个新的拓扑指标,命名为和连通指标,记作X(G)并定义为X(G)=∑uv∈E(G)1/(d_u+d_v)~(1/2).该文得到了包括图的交,并,科罗纳积,笛卡尔积,和对称差的图运算的和连通指标.     

关于顶点的棱—凝聚度的一个定理

1 引言设G是有限阶简单图。以V(G)和E(G)分别表示G的顶点集与棱集。若S是V(G)或E(G)的子集,则以G—S表示从G中删去S后所得到的图(当S={x}V(G)时,将G—S记作G-x)。如果G是连通的,而G—S不连通或者是平凡图,则称S是G的断集(当SV(G))或截集(当SE(G))。最小断集或截集的基数称为G的连通度或棱连通度,分别用K(G)和λ(G)来表示。当G为平凡图或不连通时,我们约定其连通度与棱—     

线图的几何算数指标

设 G＝（V ,E）是一个简单的连通图,V （G）和 E（G）分别是图 G 的顶点集和边集,其中｜V （G）｜＝n,｜E（G）｜＝m．Vukicˇevic＇等定义了一个新的拓扑指标———第一个几何算数指标,记作 GA1（G）．获得了线图的第一几何算数指标的上界和下界．     

线图的几何算数指标

设 G＝（V ,E）是一个简单的连通图,V （G）和 E（G）分别是图 G 的顶点集和边集,其中｜V （G）｜＝n,｜E（G）｜＝m．Vukicˇevic＇等定义了一个新的拓扑指标———第一个几何算数指标,记作 GA1（G）．获得了线图的第一几何算数指标的上界和下界．     

S(7，n)的k-边优美的图标号Z

设图G＝(V,E),其中|V|＝p,|E|＝q.对于k∈N,如果存在一个双射f：E→{k,k＋1,…,k＋q－1},使得它的导出映射f＋：V→Zp,uMT ExtraaAp(u,v) mod p也是一个双射,则称图G是k-边优美的.对于所有的满足G为k-边优美图的非负整数k构成的集合称为图G的边优美指标集.本文根据轮图的特殊性质,讨论了S(7,n)为k-边优美图的必要条件.根据所得的必要条件,利用递归的方法构造S(7,n)的k-边优美图标号并给出详细证明,从而完全解决了当n为偶数时S(7,n)的边优美指标集问题.     

有向双环网络的彩虹路连通性

设1≤s1s2n.有向双环网络G(n;s1,s2)是如下定义的有向图(V(G),E(G)):其结点集是V(G)=Zn={0,1,2,…,n-1},边集是E(G)={i→i+s1(modn),i→i+s2(modn)|i=0,1,2,…,n-1}.给出了有向双环网络G(n;s1,s2)的彩虹路连通的一个边着色方案,并给出了其彩虹路连通数上界,它主要由G(n;s1,s2)所确定的L-形瓦的2个参数表示.