图的最长路与最长圈

路和圈是图论最基本的概念之一,Euler图问题和Hamilton问题都可归结为路和圈的研究．此外,路和圈在特定图中存在条件是我们最为关注的问题,而最长路和最长圈的研究更是引人入胜．本文就此问题作了较全面的回顾,并提出一些问题,供研究、探讨。     

双繁星Wiener指标的极值

一个连通的无圈分子图（树）称为双繁星,如果删去其所有悬挂点后,得到的分子图是双星树。主要考虑双繁星的Wiener指标的极值问题,完全刻画了具有固定顶点数的双繁星的最小Wiener指标。     

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

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

Δ-free图的最长路和最长圈

得到Δ-free图的最长路和最长圈的下界为2δ＋2,以及存在Hamilton圈的一个充分条件δ≥max{ ,α},δ是图G的顶点的最小度,α是G的独立数p＝ V(G) ≥15．     

某类联图中保Wiener指数的树

Wiener指数是指一个连通图中所有顶点之间的距离之和。给定一个连通图G,若存在G中一棵子树T,使得W(G)=W(T),则称T为G的一棵保Wiener指数的树,本文给出了对于满足特定条件的某类m+2k阶联图中均有保Wiener指数的子树。     

单圈图Wiener指标的极值

一个连通图中的Wiener指标是其图中所有两个顶点之间的距离和.如果一个连通图具有相同的顶点数和边数,则称为单圈图.主要研究单圈图的Wiener指标,并刻画所有具有最大、次大Wiener指标的单圈图的特征.     

图的最长路的一个性质

本文给出了图的最长路的一个性质:设G是有n个点的2-连通图,如果对于任一对使d（u,v）=2的点u和v而推出max{d（u）,d（v）}≥c/2（3≤c≤n）,那么存在一条最长路μ=v_1v_2…v_r,且min{d（v_1）,d（v_r）}≥c/2。由此可得到图中圈长性质的一个较简单的证明。     

分裂图的Wiener指标

连通图G的Wiener指标W(G)被定义为图G中所有点对之间的距离之和。分裂图是其顶点集可以划分为独立集和团的不相交并集的图,本文给出了直径为3的分裂图的Wiener指标的计算公式。     

最长路原理与图中的路和圈

设（其中）为图Ｇ中一条最长ｙ一路，即以ｙ为终点的路中最长者．那么且对也是最长ｙ一路．利用该简单原理证明：对于２－连通非Ｈａｍｉｌｔｏｎ图Ｇ的任一顶点ｙ．存在某最长ｙ－路Ｐ（ｘ，ｙ）使ｄ（ｘ）较大．据此直接推出关于周长的范更华定理等重要结果。     

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

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

范-条件与具有给定端点的最长路

令G是n阶2-连通图且d(u,v)=2 max{d(u),d(v)}≥n/2.设{x,y}不是G的2-割集.记最长的(x,y)-路的长度为p(x,y).本文证明了如下结论:(1)p(x,y)≥n-2;(2)若p(x,y)=n-2且P是最长的(x,y)-路中使得d(xp)最小的一条,那么d(xp)=2,3或者n/2,其中xp表示唯一一个不属于P的点.本文还刻画了3-连通且使得d(xp)=3的图.     

关于最长圈交Crotschel猜想的证明

讨论了最长路的交及性质,证明了Ｇｒｏｔｓｃｈｅｌ猜想：Ｃ１和Ｃ２是ｋ－连通图Ｇ的两个最长圈,则│Ｖ（Ｃ１）∩Ｖ（Ｃ２）│≥ｋ,且公共点Ｖ（Ｃ１）∩Ｖ（Ｃ２）形成Ｇ的一个顶点割。     

具有围长g的连通图的周长

设G是具有围长g≥5,最小度δ≥2的n阶连通图,若λ=min{d(u) d(v)|u,v∈V(G),uv■E(G)},则G的周长为:■     

关于简单图的周长与围长

设G是具有围长g≥4 和最小度δ≥2 的简单图。若对于任意 u,v∈V(G),d(u,v)=2,都有 max{d(u),d(v)}≥b(≥δ),则 G的周长为     

2－连通图的最长路

设Ｇ是２－连通图，对Ｇ中任一对不相邻的顶点ｕ，ｖ，｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥ｓ．Ｆａｕｄｒｅｅ猜测，当Ｇ的顶点数　ｓ为奇数时，Ｇ的最长路的顶点数　本文证明猜测当ｓ＞３时是真的．进而证明了除一类图外Ｐ（Ｇ）≥ｍｉｎ｛｜ｖ（Ｇ）｜，２ｓ＋ｌ｝．     

n阶单圈图的边平均Wiener指标

对于n阶单圈图的边平均Wiener指标,证明了当n≥6时,W’e(G)≤112(2n3-32n+69),等号成立当且仅当G≌C3(Pn-2);W’e(G)≥14(2n2-9),等号成立当且仅当G≌C3(Sn-2)。     

3—连通无爪图的Hamilton—连通性

设Ｇ是ｎ阶３－连通无爪图，δ是其最小次，若ｎ≤４δ－８，则Ｇ是Ｈａｍｉｌｔｏｎ连图。