.290. 北京科技大学学报 1994年No.3 2-连通Oe-(-2)型图G有一个Hamilton图除非G是图1中所示的图(a)与(b)之一·本 文将改进上述两个结果，得到了一个有边不交的3个1-因子的新充分条件，即2阶1≥10) 2-连通且(G)≥4的Oe-(-2)型图G有边不交的一个Hamilton圈和一个1-因子除非G 是附图中所示的图之一. 1引理 为了证明本文的主要定理，先引进一些引理， 引理1171.设G是2n阶2-连通Ore-(-2)型图(n≥6).则G有一个Hamilton圈除非 G是附图的(a)和(b)中所示的图之一. 引理2161.设G是n阶具有ax(G)≤δ(G)的简单图，u.v是G中不相邻的一对顶点，令8。(u,D) =n一d(u)-d(o).R。(u,t)={x5R(u,):d(x)≥6e(u,v)+2}.如果IR。(4,川≥6e(u,),且 k(G)≥2.则G是Hamilton图当且仅当G+uv是Hamilton图. 引理31，设G是n阶具有x(G)≤(G)且k(G)≥1的简单图，u和v是G中不相邻的一 对顶点，如果d(u)+d(o)≥n(k(G)-l,那么G是Hamilton图当且仅当G+是Hamilton图. 图G在引理2和3下的闭色用G表示. 引理4.设G是2n阶2-连通Ore-(-2)型图，令X={xtV(G):d(x)≤n-2)则1X)≤ n-1且G[X灯为完全图， 引理4，的证明较简单，在此略证， 引理5.设G是2n(n≥10)阶2-连通Ore-(-2)型图且6(G)≥4.如果G不是图1中所示 的图之一，则G有一个1-因子N使得G-N为2-连通. 证明：由引理1可知G中有一个1-因子N.令G=G-N.X={xV(G):d(x)≤n-3, Y=V(G)-X.由引理4可知X≤n-1且G[灯为完全图.如果G'是2-连通，则引理已 证.因此设G不是2-连通.下面分两种情形来证明， 情形1·G'不连通. 显然，G'只有两个分支G和G,且|V(G,)川≥4(=1,2).如果G,中含有Y中的点，则V(G)川 ≥n-1.如果G,和G,中含有X中点，则G,和G,只能含有1个X中的点，否则G连通.下 面再分两种情况来证明· 1)G,和G2同时含有Y中点.则1V(G,)1≥n-1,(i=1,2) (a)IV(G)1=n-1,则1V(G)川=n+1. 这时△(G,)≤n-2而且△(G)≤n.对于X中任何一点“，如果u∈V(G),则在G:中必有一 点t使得uw年E(G),于是d(0)+d(w)≥2n-2,从而dG(m≥2n-2-1-(n+1)=n-4,因 此δ(G)≥n-4≥|V(G)/2+1.同理可证如果u∈V(G,则d。(u)≥n-3,从而δ(G)≥n-3 1V(G,)川/2+1.故G,和G均为Hamilton连通.如果N中有至少3条边e,=u,v,(i=1,2,3, u,∈V(G),V,∈V(G)连结G,和G,则在G,中有一条Hamilton路Pc,(4,4)连结4，和42， 在G,中有一条Hamilton路PG,(心，马)连结和，于是C=Pc,(,儿U{4,}UPc,(,) 是G中的Hamilton圈，从而在C上可选取G中的一个】-因子N',使得e,N',于是还容 易证明G,和G,都有Hamilton圈而且e2和e连结它们，故G-N为2-连通.如果N中恰· · 北 京 科 技 大 学 学 报 望科 年 一 连通 一 一 型 图 有 一 个 五 图除非 是 图 中所示 的 图 与 之 一 本 文 将 改 进 上 述 两 个结 果 ， 得 到 了一个有 边不交 的 个 一 因子 的新充分 条件 ， 即 阶 。 一 连 通 且 占 的 一 一 型 图 有 边 不交 的一 个 圈 和 一 个 一 因 子 除 非 是 附 图 中所示 的 图之 一 引 理 为 了证 明本 文 的主要 定理 ， 先 引进 一些 引理 引理 设 是 阶 一 连通 一 一 型 图 则 有 一 个 耐 圈 除 非 是 附 图 的 和 中所示 的 图之 一 引理 ’ “ ， 设 是 阶具有 城 簇 占 的简单 图 ， ， 。 是 中不相邻的一对顶点 ， 令 日仄 ， 。 一 。 一 ， 。 ， 。 一 、 任 。 ， 口。 ， 如果 。 ， 。 ， ， 且 峨 则 是 耐 图 当且 仅 当 。 。 是 图 引理 ’‘ ， 设 是 。 阶具 有 城 毛 侧 且 的 简 单 图 ， 。 和 是 中不 相 邻 的一 对顶 点 如果 伪 一 一 ， 那 么 是 耐 图 当且仅 当 。 。 是 图 图 在 引理 和 下 的 闭色 用 表示 引理 设 是 阶 一 连通 一 一 型 图 ， 令 资 分 簇。 一 ， 则 簇 一 且 月 为完全 图 引理 的证 明较 简单 ， 在此 略证 引理 设 是 阶 一 连通 一 一 型 图且 占 如果 不是图 中所示 的 图之 一 ， 则 有 一 个 一 因 子 使得 一 为 一 连通 证 明 由引理 可 知 中有 一 个 一 因 子 令 口 二 一 ， 、 任以 劝 簇。 一 ， 一 由引理 可 知 簇 一 且 月 为 完 全 图 如 果 ‘ 是 一 连 通 ， 则 引理 已 证 因此设 ‘ 不 是 一 连通 下 面分 两种情形 来证 明 情形 ’ 不连通 显然 ， ‘只有 两个分 支 和 ， 且 ， 如果 ， 中含有 中的点 ， 则 川 一 如果 ， 和 中含 有 中点 ， 则 和 只能含有 个 中的点 ， 否 则 ‘ 连通 下 面再分 两 种情 况来证 明 ， 和 同时含有 中点 则 ， 一 ， ， 一 ， 则 这 时 △ 一 而且 △ 毛 对于 中任何 一 点 ， 如 果 “ 任 【 ， 则 在 中必 有 一 点 使得 诺 ， 于 是 一 ， 从 而 。 一 一 一 。 一 ， 因 此 占 一 同理 可 证 如果 。 份 ， 则 。 一 ， 从 而 占 一 故 ， 和 均 为 耐 连通 如果 中有 至 少 条 边 ， ， ， ， ， ， 呀 ， 矶任 连结 ， 和 ， 则在 中有 一 条 耐 路 。 ， 连 结 和 ， 在 中有 一条 耐 路 。 ，， 连结 、 和 ， 于 是 一 。 “ ， 日 ， ，， 日 ， 叼 是 中的 圈 ， 从而 在 上 可 选取 中的一 个 一 因 子 ’ ， 使 得 砖 ’ ， 于 是 还 容 易证 明 ， 和 都有 耐 圈而且 马 和 连结 它 们 ， 故 一 丫 为 一 连 通 如 果 中恰