单圈图关于和连通度指标的最大值的排序

和连通指标是指图G的边的权的总和,这里边uv的权等于(dG(u)+dG(ν))-12,dG(u)表示点u的度。文章得到了恰好含有三条悬挂路的单圈图的和连通度指标的可达上界,也确定了和连通度指标的第二到第八最大值的单圈图。

给定阶、直径和悬挂点数的树的谱半径

研究了在阶为n、直径为d且悬挂点数为s的所有树中,树具有最大的谱半径问题.令Pd+1是一个d+1阶的固定路,Tn,d,s表示通过在Pd+1的第r个顶点生成s-2条几乎等长的路得到的阶为n、直径为d且悬挂点数为s的树,其中r=r(d)是(d+1)/2的整数部分,则Tn,d,s具有最大谱半径.该结论推广了给定阶、直径或悬挂点数的树的谱半径的一些结果.借助该结论,也得到了树的谱半径与其独立数、覆盖数、边覆盖数和全独立数之间的关系.

双圈图关于和连通度指标的最大值的排序

和连通度指标是指图G的边的权的总和,这里边uν的权等于(d_G(u)+d_G(ν))-1/2,d_G(u)表示点u的度。研究得到了恰好含有一条悬挂路的和连通度指标第一最大及第二最大的双圈图,并对双圈图按照和连通度指数的第三及第四最大值进行排序。

单圈图的极小ABC指数

给出了取得极小ABC指数单圈图的结构性质,通过图形变换、分式比较,给出了n阶3-圈图与取得极小ABC指数的n阶单圈图的关系.

一种基于悬挂顶点关联索引的最短路径查询算法

最短路径查询是图数据查询中的热点问题。针对现有的"索引+查询"方法存在的查询效率低下且扩展性差等问题,本文提出了悬挂顶点关联索引策略,即先对度为1的顶点构建顶点关联索引,再对其他顶点构建2-hop标签索引,并依此提出了相应的最短路径查询算法。本文提出的索引策略降低了索引规模,减少了构建索引时间,使得最短路径查询算法的效率和扩展性得到了改善。最后,通过对11个真实的数据集进行实验,从索引构建时间、索引规模大小、查询时间等方面验证了本文方法的高效性。

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

设G^(σ)是n阶定向单圈图,S(G^(σ))是其斜邻接矩阵.图G^(σ)的斜秩sr(G^(σ))定义为其斜邻接矩阵S(G^(σ))的秩,图G^(σ)的围长,记为g(G),定义为其底图G中最短圈的长度.刻画了斜秩等于围长的定向单圈图.