图的割点的矩阵判别

本文给出一种寻找图的割点的矩阵方法，即利用图的邻接矩阵Ａ及矩阵Ａ＾ｃｕ＝（１，…，ｉ－１，ｉ＋１，…ｎ１，…，ｉ－１，ｉ＋１，…，ｎ）（ｉ＝１，２，…，ｎ）。     

含一个割点的连通图的最小特征值

一个图的无符号拉普拉斯最小特征值在某个图类中的所有图中达到最大时常称为极大图;通过利用特征向量方程研究特征值的方法,对只含有一个割点的连通图的无符号拉普拉斯最小特征值进行了研究,且得到了最小特征值的值,从而得到了只含有一个割点的具有相同阶数的所有的连通图中最小特征值的极大值,并且刻画了最小特征值取到极大值时所对应的极大图的结构.     

点可迁图的顶点划分

设G是k正则连通点可迁图。图G的一个边割S称为限制性边割，如果G－S不含孤立点，最小限制性边割所含的边数λ′称为限制性边连通度。已经证明λ′≤2k-2，等号成立时，称图G是极大限制性边连通的。本文证明了：如果G不是极大限制性边连通的，那么G的顶点集存在一个划分π＝（C1，…，Cm)，使得由Ch导出的子图同构于一个连通k-1正则点可迁图H,h=1,2，…，m，而且k≤|H|≤2k-3。     

2-连通图中点不交路的划分问题

给定一个阶为n的2-连通图G=(V;E)及一个正整数k,考虑在邻域并条件下G被分成k条点不交路的问题,得到下面的结果,对G中任何四个独立点x1,x2,y1,y2∈V,满足|NG(x1)∪NG(x2)| |NG(y1)∪NG(y2)|n-k,则G能被分划分k条点不交的路.     

利用块割点树计算六环螺链的Wiener指标

文章利用块割点树讨论了六环螺链(又称六元素环螺链)Gn的Wiener指标W(Gn)的计算问题.并给出了W(Gn)的计算表达式和极值.     

链状割点图的Hosoya多项式

任一连通图的Hosoya多项式的定义如下:H(G)≡H(G,x):=∑d(G,k)xk k≥0,其中d(G,k)是图G中距离为k的点对的个数。事实上,d(G,0)等于图G的点数,而d(G,k)等于图G的边数。设{Gi}ni=1是一个两两不交的图的集合,并且Vi,Vi∈V(Gi),所谓链图C(G1,G2,…,Gn)≡C(G1,G2,…Gn;v1,w1,v2,w2,…,vn,wn)指的是将各点对wi和vi+1粘合起来而得到的图,其中i=1,2,…,n-1。文章得到了链状割点图的Hosoya多项式,并且,作为引理,并给出了树的Hosoya多项式。     

含割点的连通图的最小距离无符号Laplace谱半径

在含割点的n阶连通图类中,通过运用特征向量研究特征值的方法,确定了具有最小距离无符号Laplace谱半径的唯一的图,并且给出了距离无符号Laplace谱半径关于阶数n的一个下界.     

拟(k+1)-连通图的一些性质

设G为κ－连勇图且不存在非平凡的κ－点割,则称G为拟（κ＋1）－连通图,给出了拟（κ＋1）－连通图的一些类似于（κ＋1）－连通图的性质。     

k连通图在边点割原子与点割上的可去边

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割断片的性质给出某些k连通图中在特定子图上可去边的分布情况,得到了最小度至少为(3(k-1)/2)或围长至少为4的k连通图(k≥4)中由边点割原子与点割所导出的子图的每一条边都是可去边.     

图的邻点可区别边划分(英)

研究了图的邻点可区别边划分所需要的最少边色数. 通过对图的度进行分类讨论, 证明了不包含$K_{2}$且最小度$\geqslant188$的图有邻点可区别点染色3边划分. 这个结论比已有结果更优越     

一个基于谱图分割的简单聚类算法

目前谱聚类在文本分类、图像分割和信息检索等领域的应用越来越引起研究者的重视,并取得了一定的成果、但是,大多数已有的谱聚类算法需要事先给定聚类数．在k-means算法、EM等聚类方法中也存在相似的问题、在此介绍了一种简单的容易实现的谱聚类算法,可以自动确定合适的聚类数．实验表明本算法结果很好、     

简单无向连通图的k阶幂图的指数集

设Ｇ为简单无向图，以Ｖ＝Ｖ（Ｇ）为顶点集，以Ｅ＝｛（ｕ，ｖ）｜ｄ（ｕ，ｖ）≤ｋ｝为边集的图称为Ｇ的ｋ阶幂图。ｎ阶简单无向连通图的ｋ（ｋ≥２）阶幂图的指数集。     

Ferrers图在正整数拆分中的应用

<正>整数的拆分与许多计数问题有着密切的关系.文章运用Ferrers图讨论了正整数拆分问题,得到正整数拆分的共轭拆分表达式,证明了正整数进行拆分的拆分数,可转化为求较小数n-m(m+1)/2的拆分数.     

关于图的顶点划分数

该文讨论了无爪图的顶点划分数,给出了完全n部图的顶点划分数的计算公式,最后证明了任意图的点线荫度不大于它的边线荫度且不等式是精确的.     

连通图二次幂图的Hamilton连通性

本文对圈和树的二次幂图的 Hamilton 连通性进行了研究。     

判定k-点连通图与k-边连通图极小性的定理

主要研究了判定ｋ－点连通图是极小的充要条件和ｋ－边连通图是极小的必要条件。     

连通交错单群的素图刻画

设G是个有限群,给出了群G的素图.利用素图的性质,首次对连通的有限单群进行刻画,得到了与交错单群Alt22的素图一样的有限群的结构.     

图中水晶覆盖数的上下界

通过对简单图中水晶覆盖数的研究，得出了连通图G和连通图G-e间水晶覆盖数的关系，进而得到了连通图水晶覆盖数的上界和下界．     

关于图的单圈划分

图的划分问题曾引起图论界的广泛关注 ,本文讨论了一般的单圈划分问题 ,利用禁用构形刻划了一个图存在单圈划分的条件 ,并进一步得到一个算法 ,有效地解决了判定一个图是否存在单圈划分 ,若存在则求其单圈划分的问题 .     

连通图的平均距离

图的直径是图中两点距离的最大值,图G的平均距离,记作D(G),它是图的任两点距离的平均值。在网络分析中,图的直径和平均距离是重要的示性数。该文对某些较简单的图类:简单圈、树等的平均距离进行估算,证明了若G是直径不超过3的n阶连通图,则它的平均距离至多是n/δ+1,这里δ是G的最小度。最后,对n阶连通图的平均距离的上界提出了一个猜测