树与它的公共邻点图之间的维纳指标的差（英文）

一个连通图的维纳指标被定义为所有无序顶点对之间的距离和.如果G是一个简单图,那么con(G)是图G的公共邻点图,它们有相同的顶点集,并且在图G里如果两个顶点有一个公共邻点,则在图G的公共邻点图里这两个顶点是相邻的.该文得到了关于树和它的公共邻点图的维纳指标之间差的下界和上界.     

树图的外围维纳指标的下界

设G=(V,E)为简单连通图.对v∈V(G),顶点v的离心率ε(v)=max{d(u,v)│u∈V(G)}, d(u,v)为图G中顶点u,v间的距离.图G的直径为d(G)=max{ε(v)│v∈V(G)}.外围顶点集P(G)指图G中满足ε(v)=d(G)的所有v=V(G).图G的外围维纳指标为■.首先讨论了当树图T的外围顶点个数确定时,它的第二下界;然后讨论了当树图T的顶点数目确定时,其对应的PW(T)的最小值,及达到其最小值的极图.     

完美匹配单圈图的维纳指数

主要研究单圈图的维纳指数的性质.给出阶数为2β的完美匹配单圈图的维纳指数下界,并刻画了达到下界的所有极图.     

在直径为d的树中具有极小GA2的树

Tabar等人定义了图的第二类几何-算术指标GA2,同时给出了任意连通图G的可达上下界,并分别刻画了：在有n个顶点的树中Pn具有极大GA2,K1,n-1具有极小GA2.刘颖在有n个顶点的树中确定了具有GA2前五小的图及在具有完美匹配的所有树中具有GA2前四小的图.在此基础上,本文给出直径固定且有n个顶点的树中具有极小GA2的图.     

具有完美匹配且直径不大于7的强优美树

一棵具有n个顶点且有完美匹配M的树T,若有一个优美标号f使得对T的每条边uv∈M都有f(u)+f(v)=n-1,则称树T是强优美的.证明所有直径不大于7且有完美匹配的树都是强优美的,并给出了一种构造大的强优美树的方法.     

给定分支点数目树的离心率总和

设G=(V,E)是简单连通图,简单连通图G的离心率总和定义为图G中所有顶点的离心率总和。若树T中某个顶点的度大于等于3,则称这个点为T的分支点。刻画了给定分支点数为r顶点数为n的树的离心率总和的上界和下界。     

给定度序列的毛毛虫图的维纳指标

一个连通图的维纳指标定义为它的所有不同顶点对之间距离的和。给出图的两个变换以及计算这两个变换下新图维纳指标的公式,借助这两个变换刻划所有给定度序列的毛毛虫图中具有最小维纳指标的图。     

给定最大匹配数的树的零阶广义Randi(c)指标的界

图G的零阶广义Randi(c)指标定义为R.(G)=∑v(E)V(G)d(v),其中d(v)为G的顶点v的度,α为非零实数.当-1≤α＜1,α≠0时,本文确定了给定最大匹配大小的一类树图的零阶广义Ranaic指标的界,并给出了达到最小值和最大值的树图的刻划.     

给定直径和悬挂点数的树的拉普拉斯系数

令φ(T,λ)=∑nk=0(-1)kck(T)λn-k是一个n点树T的拉普拉斯矩阵的特征多项式。熟知,cn-2(T)和cn-3(T)分别等于T的维纳指标和修改超维纳指标。应用图的变换,确定给定直径和悬挂点数的树中所有拉普拉斯系数ck(T)最小的树。特别是确定了一些具有极端维纳指标、修改超维纳指标和Laplacian-like能量的树。     

极大外平面图与树状三角系统和四角系统的完美匹配

给出了计算路状四角系统完美匹配数的标数字法,并得到如下一些图类完美匹配数的紧上、下界:1)2n阶(n≥2)极大外平面图完美匹配数的紧上、下界分别为fn和2;2)具有2n个细胞(n≥1)的树状三角系统完美匹配数的紧上、下界分别为fn 1和2;3)具有n个细胞(n≥1)的树状四角系统的完美匹配的紧上、下界分别为fn 1和n 1,以上fn表示Fibonacci数列{fn}n≥0的第n项.     

关于树和单圈图的第k大特征值

设T是kt＋l（k≥2，0＜l＜k）顶点树，G是n顶点单圈图。本文得到了l＝1时T的第k大特征值上界极图的某些性质，并且给出了G的第k（1＜k＜［n／2］）大特征值的一个上界和一个下界。     

路与路的强积的r-多彩染色

基于图的特征和图的顶点度的性质,分析得出路与路的强积PmPn(m、n为正整数)的r-多彩色数的下界,对于不同的正整数r,通过构造图的r-多彩染色得到其多彩色数的上界,从而确定了所有PmPn的r-多彩色数.     

一类笛卡儿乘积图的PM-紧邻性质

图G的完美匹配图,记为PM(G),是以G的每个完美匹配作为顶点并且两个顶点相邻当且仅当这两点对应于G中两个完美匹配的对称差恰好是一个圈而得到的图.若PM(G)是完全图,则称G是完美匹配紧邻的,简称G是PM-紧邻的.研究了一类笛卡儿乘积图的PM-紧邻性质,完全刻画在这类笛卡儿乘积图中所有的PM-紧邻图.     

单圈图的k-距离匹配控制数

单圈图是边数等于顶点数的连通图.令G=(V,E)是无孤立顶点的图,若集合DV(G)是G的一个k-距离控制集且导出子图〈D〉有完美匹配,则称D是G的一个k-距离匹配控制集.k-距离匹配控制数γkp(G)是G的最小k-距离匹配控制集的势.主要证明了单圈图k-距离匹配控制数的一个重要引理,由此找到了单圈图k-距离匹配控制数的上界,并构造了极图.     

Kneser图KG(11,5)平方图的色数

Kneser图KG(n,k)的顶点集包括一个n元集的所有k元子集,其中的任意两个顶点相邻当且仅当它们对应的子集不相交.一个图G的平方图G2的顶点集与G的顶点集相同,在G2中两个顶点之间有边当且仅当它们在G中的距离不超过2.通过理论分析和计算机搜索,得到8≤χ(KG2(11,5))≤10,10≤χ(KG2(13,6))≤16,其中前一个结论改进了已知的下界7和上界12.     

4元n方体的匹配图的若干性质

一个图G的匹配图M(G)的顶点集是G的所有完美匹配的集合,两个顶点相邻当且仅当对应的两个完善匹配的并构成G的一个Hamilton圈.文章给出了4元n方体Qn4的匹配图M(Qn4)的一些性质.     

循环图的Laplacian Estrada指数

设G是一个具有n个顶点的简单循环图,它的Laplacian特征值为μ≥μ≥...≥μ_≥μ=0,图G的Laplacian Estrada指数定义为EEG(G)=∑=eu.利用分析的方法,得到了循环图的Laplacian Estrada指数的一个较为精确的上界和下界.     

关于树图的谱半径的界

给出了由边数为m、顶点数为n的简单连通图G生成的树图T(G)及邻树图T^*(G)的谱半径的上界：ρ（T（G））≤det(Hr(G))(1-1/m) ρ(T^*(G))≤det(Hr(G))(1-1/x′（G））其中x′（G）是图G的边色数;并指出当G≌Cn时,ρ（T（G））的上界可达。     

Kn,n的限制均匀边染色

给出图G和一个正整数r,令f‘r(G)为图G边染色的最大色数,使得每个顶点最多关联r种颜色,并且每个顶点关联的颜色中任两种颜色所染的边数相差最多为1．对所有的正整数n和r,给出了f‘r(Kn,n)的下界和上界;在r|n和r=2,3,n-1的情形,得到f‘r(Kn,n)的值。     

关于树的Wiener维数的一个注记

一个连通图G的Wiener维数是指G的所有不同的顶点距离的数目。设T是一个树,diam(T)是T的直径。得到了T的Wiener维数的一个紧的下界为|diam(T)/2|+1。