竞赛图中的最长圈问题

若有向图T满足条件:uv■A(T)使得d T(u) dT-(v)≥k,则称图T满足O(k)条件.在该文中,笔者讨论了竞赛图的最长圈,并且给出了某些有向图的Hamilton圈的存在条件.     

特定竞赛图中的最长圈问题

若有向图T满足条件:uv(≠)A(T)使得dT (u) dr-(v)≥k,则称图T满足O(k)条件.讨论了有向图及特殊有向图的最长圈,并且给出了某些特殊竞赛图的Hamilton圈的存在条件.     

二部竞赛图中的最长圈问题

证明了以下结论:对于一个p×q阶二部竞赛图T,如果T(p,q)满足L(n)条件且强连通,则T包含一条长至少为2min{n+1,p,q}的圈,除非T同构于一类特殊的图族。     

有向图的最长圈

讨论了有向简单图的最长图,并给出某些图的Hamilton路和Hamilton图的存在条件。     

二连通图的最长圈

本文证明:设G为n阶2连通图,D(x)={y|y∈V(G),d(x,y)≤2},d_d~*(x)表示D(x)中所有的点的度排成的非减度序列:d_1~*,d_2~*,…,d_j~*,d_(j+1)~*,…,d_(|D(x)|)~*中当下标j=d(x)时的度。δ_0=min{d(x)|x∈V(G)},D(δ_(i-1))={x|x∈V(G),d(x)≥δ(i-1)}(i=1,2,…,k),δ_i=min{d_(d(x))~*|x∈D(δ(i-1))}(i=1,2,…,k)且δ_0<δ_1<δ_2<…<δ_(k-1)≤δ_k,则C(G)≥min{n,2δ_k}。此外也给出δ_k的算法。     

Hamiltonian二部竞赛图中的充分条件

证明了对于一个n×n阶二部竞赛图T,如果T(n,n)满足W(n)条件,则T(n,n)中包含长为4,6,2n的圈,除非T同构于一类特殊的图族.     

圆可分解的局部竞赛图中的点外弧泛圈问题

Yao Tianxing(Discrete Appl．Math．，2000，99：245-249)已经证明了每一个强连通竞赛图都包含点，它的每条外弧都是泛圈的．将此结论推广到强连通的圆可分解的严格局部竞赛图，并证明了每一个强连通的圆可分解的严格局部竞赛图D，它的圆分解是D=R[D1，D2，…，Da]，其中Di，i=1，2，…，a是强连通竞赛图，那么D包含一个点v，它的每条外弧是(g 1)-泛圈的，g=max{l(Ca)|Ca是包含a的最长诱导圈，a∈V(R)，l(Ca)是Ca的长度}。     

有向圈卡氏积图的哈密尔顿圈

讨论两个有向圈Cn与Cm的卡氏积图Cn×Cm的Hamilton性,给出并证明了:Cn×Cm存在有向Hamilton路,但未必存在有向Hamilton圈;当n｜m时,Cn×Cm必存在有向Hamilton圈.     

一类图中的最长圈

引言 Dirac曾经证明,如果简单图G的最小次δ满足δ≥|G|/2,则G是Hamilton图。记为G∈H。Ore改进到,若f=min{d(u)+d(v)|uv(?)E(G)}≥|G|,则G∈H,Jung[1]又改进到,若,则G∈H。这里S是V(G)的真子集,G/S是从G中除去S所得的图,K(G/S)是图G/S的连通分支的数目,最小是在所有K(G/S)≥2的S上取的。     

图的最长路与最长圈

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

关于边染色竞赛图中的最长单色路

证明了如下结果：设T为顶点数至少为4（3k 1) 2竞赛图，其每边染上红或绿两种颜色中的一种颜色，则T中存在一长长度至少为k的单色有向路。     

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

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

连通[5,3]-图的最长圈

如果G中任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图。现证明以下定理:设G是n(≥7)阶连通[5,3]-图,则G中最长圈的长度不小于[n/2],此界是最好可能的。     

均匀多部竞赛图的分量共轭圈问题

GUO Yubao和Volkmann证明了一个2-强连通多部竞赛图包含两个分量共轭圈,使得每部至少有一个点在其中的一个圈中.得到的结论是Guo和Volkmann的定理的进一步推广.     

4连通无爪图的最长圈

设Ｇ为ｎ阶４连通远爪图，δ＝ｍｉｎ（ｄ（ｘ）／ｘ∈Ｖ（Ｇ）），则当ｎ≤６δ－１１时Ｇ为Ｈ图，当ｎ≥６δ－１０时，ｃ（Ｇ）≥５δ－７。     

一类图的最长圈

设Ｇ是２－连通图。对Ｇ中任一对不相邻的顶点ｕ,ｖ,│Ｎ（ｕ）ＵＮ（ｖ）│≥ｓ当ｓ≥５时,对于事任意两个不主的点集Ｅ,Ｆ,│Ｅ│≥ｓ,│Ｆ│≥ｓ／２,Ｇ中有３条点不交的Ｅ－Ｆ路,由Ｇ的最长圈的长ｃ（Ｇ）≥ｍｉｎ｛│Ｖ（Ｇ）│,３ｓ／２｝。     

关于1坚韧图的最长圈

令G 是 p 阶 1坚韧图,且λ=min{d(u)+d(v))|u,v∈V(G);uv∈E},δ=min{d(u)|u∈V(G)},本文证明G的周长 c(G)=p,若 P≤2λ-2δ+2;c(G)≥2λ-2δ+2,若 p>2λ-2δ+2。对某些图来说 c(G)的下界是可以达到的。