关于Faudree定理的一个注记

假定Ｇ是顶点数的ｎ的２－连通图，Ｇ中顶点数为４且包含爪Ｋ１．３的子图称为爪型子图。本文证明了对Ｇ的任一爪型图Ｆ，任何ｕ，ｖ属于Ｖ（Ｆ），由距离ｄ（ｕ，ｖ）＝２＝│Ｎ（ｕ）ＵＮ（ｖ）│≥２ｎ－１／３，则Ｇ是哈密顿图。     

关于2—连通图的最长圈

若G是2-连通图,如对G中任何两个距离为2的点υ,ν都有d(υ)+d(ν)≥λ-1(5≤λ≤|V(G)|),则除了两类图外,G的最长圈的长至少为λ。     

一类图的最长圈

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

2-连通图的最长圈

设G是2-连通图,λ(G)=min{d(u)+d(v)|u,v∈V(G),uv■E(G)},本文证明了除六类图外,G中最长圈的长c(G)≥min{|v(G)|,λ+2}。     

正则2-连通图的最长圈

P.Erdos和A M Hobbs在[1]中提出如下的结论:设k≥6,G是2k个顶点的(k-2)次正则的2-连通图,则G是Hamilton图(以下简称为H图)。本文提出比上述结论更为广泛的定理:定理1 设k≥4,G是n个顶点的(k-2)次正则的2-连通图,则除G是peterson图外,G必有个长至少为min{n,2k}的圈。由于:(i)定理1中的k=4时,G是2-正则2-连通图,G是H图,它有个长为n≥min{n,2k}的圈;(ii)定理1中的k≥5且n≤3(k-2)时,根据[2]中的B.Jackson定理知,这时G是H图,它有个长为n≥min{n,2k}的圈。因此,要证明定理1成立,只要证明如下的定理2成立。定理2 设n≥3k-5≥2k,G是n个顶点的(k-2)次正则的2-连通图,则除G是Peterson图外,G必有个长至少为2k的圈。在证明定理2的过程中,本文作下列的假设:     

2－连通图的最长路

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

关于2—连通图哈密顿路的Lindquester猜测

本文证明了Lindquester猜测:设G是顶点数为n的2-连通图,如果对于G中任一对顶点u,v,距离d(u,v)=2|N(u)U N(v)|≥(n-1)/2,则G有哈密顿路。