圖中包含4-圈和6-圈的[1,2]-因子

魯富榮

(山西大學(xué) 商務(wù)學(xué)院 基礎(chǔ)教學(xué)部,山西 太原 030031)

?

圖中包含4-圈和6-圈的[1,2]-因子

魯富榮

(山西大學(xué) 商務(wù)學(xué)院 基礎(chǔ)教學(xué)部,山西 太原 030031)

設(shè)k為一個(gè)正整數(shù),圖G是一個(gè)頂點(diǎn)數(shù)為4k的簡(jiǎn)單圖,當(dāng)δ(G)≥2k+1時(shí),文章證明了圖G包含一個(gè)由k-3個(gè)4-圈,一個(gè)6-圈及一條至少包含三條弦的6-路構(gòu)成的[1,2]-因子．

[1,2]-因子;最小度;圈

0 引言

一條邊e=uv稱(chēng)之為一條路P的弦,若有{u,v}?V(P),e?E(P)．

1984年Zahar[2]作出了如下猜想:若圖G的頂點(diǎn)數(shù)為n=n1+n2+…+nk且滿(mǎn)足δ(G)≥「n1/2」+「n2/2」+…+「nk/2」,則G包含k個(gè)相互獨(dú)立的長(zhǎng)度分別為n1,n2,…,nk的圈.

在此基礎(chǔ)上Erdos and Faudree[3]猜想如果圖G是一個(gè)頂點(diǎn)數(shù)為4k的圖,且δ(G)≥2k,則圖G包含k個(gè)頂點(diǎn)不相交的4-圈．H.Wang在2010年給出了上述猜想的證明．

定理[3]|G|=4k.如果δ(G)≥2k,則G包含k個(gè)相互獨(dú)立的4-圈．

引文[4]進(jìn)一步給出了下面的結(jié)論:

對(duì)于滿(mǎn)足|G|=4k的圖G,如果δ(G)≥2k+4,則G包含k-3個(gè)4-圈和2個(gè)6-圈,使得這k-1個(gè)圈是相互獨(dú)立的．

本文在上述工作的基礎(chǔ)上證明了如下結(jié)論:

定理1 對(duì)于簡(jiǎn)單圖G, |G|=4k,δ(G)≥2k+1,圖G包含k-3個(gè)4-圈,一個(gè)6-圈及一條至少包含三條弦的6-路(k≥3).

1 引理及其證明

引理1 設(shè)圖G包含一個(gè)4-圈C=x1x2x3x4x1和與之獨(dú)立的兩個(gè)頂點(diǎn)x,y,若d(x,C)+d(y,C)≥5,則C∪{x,y}生成的子圖中包含一條長(zhǎng)為5的含6個(gè)頂點(diǎn)的路,且6-路至少包含三條弦．

證明 不妨設(shè)d(x,C)≥d(y,C),則有d(x,C)≥3,由對(duì)稱(chēng)性,不妨設(shè){x1,x2,x3}?N(x,C),因此xx1,xx3∈E(G),又因?yàn)閐(x,C)≤4,故d(y,C)≥1,若yx4∈E(G)時(shí),則圖G包含6-路xx1x2x3x4y,且包含弦xx2,xx3,x1x4．若yx2∈E(G),類(lèi)似可得結(jié)論．若yx1∈E(G)時(shí),則圖G包含6-路xx2x3x4x1y,同時(shí)圖G包含弦xx1,xx3,x1x2．若yx3∈E(G),類(lèi)似可得結(jié)論．

2 定理及其證明

定理1 對(duì)于簡(jiǎn)單圖G,|G|=4k,δ(G)≥2k+1,圖G包含k-3個(gè)4-圈,一個(gè)6-圈及一條長(zhǎng)為6的路(k≥3).

情形1.1 若d(x1,Cj)=2時(shí),對(duì)于k=2,3,4,d(xk,Cj)=2時(shí),由對(duì)稱(chēng)性,設(shè)x1y1∈E(G),此時(shí)若有x2y2或x2y4∈E(G),則可得在G[vC1∪Cj)]中存在一個(gè)6-圈和與之獨(dú)立的一條邊e,若設(shè)e=uυ,H1=G-C1-Cj,則有d(u,H1)+d(v,H1)≥4k+2-14=4(k-3).

當(dāng)k=3時(shí),設(shè)C2=y1y2y3y4y1,C3=z1z2z3z4z1,Cj=C2,且有x1y1或x4y2∈E(G),若e(y3y4,C3)≥1,則可得結(jié)論,故我們只需考慮e(y3y4,C3)=0的情形，由于δ(G)≥7,故有d(y3,C1)=d(y4,C1)=4,故由類(lèi)似討論可知d(y1,C3)=d(y2,C3)=0,因此e(C1,C3)=12.此時(shí)易得結(jié)論．

當(dāng)k>3 時(shí),d(u,H1)+d(v,H1)≥4(k-3)≥4,則在H1中至少存在一個(gè)圈C′,使得d(x3,C′)+d(x4,C′)≥1,故有G[VC′∪{x3,x4})]含一條包含6個(gè)頂點(diǎn)的路,此時(shí)結(jié)論成立.

因此,由對(duì)稱(chēng)性,若有x4y2或x4y4∈E(G),同理可證結(jié)論成立.因此只能有x4y1,x4y3∈E(G),同理有x2y1,x2y3∈E(G),故e(x2,C2)=e(x4,C2)={y1,y3},x4y2,x4y4?E(G),x2y2,x2y4?E(G),同理由對(duì)稱(chēng)性,由于x4y1,x4y3∈E(G),故e(x1,C2)=e(x3,C2)={y1,y3},故d(x4,H1)+d(y2,H1)≥4k+2-(3+2+3)=4k-6>4(k-2).也即在H1的k-2個(gè)4-圈中至少存在一個(gè)4-圈C1,使得d(x4,C1)+d(y2,C1)≥5.由引理1,C1∪{x4,y2}生成的子圖中包含一條長(zhǎng)為5的含6個(gè)頂點(diǎn)的路P,且路P至少包含3條弦,結(jié)論得證．

[1] BONDY J R,MURTY U S R. Graph theory with applications[M].Amsterdam:North-Holland,1976

[2] ELZAHAR M H.On circuits in graphs[J].Discrete Math,1984,50:227-230

[3] WANG Hong.On the maximum number of independent cycles in a Bipartite Graph[J]. Journal of Combinatorial Theory, Series B,1996,67,152-164

[4] LU Furong. Disjoint 6-cycles and 4-cycles in graphs[J].Journal of Taiyuan Normal University,2012,4:10-11

A [1,2]-Factor Containing Disjoint 6-Cycles and 4-Cycles in Graph

LU Furong

(Business College of Shanxi University, Taiyuan 030031, China)

Letk≥3 be a positive integer.LetG=(X,Y;E)be a graph with |G|=4k.Supposingδ(G)≥2k+1,then G has a spanning subgraph consisting ofk-3 quadrilaterals, one 6-cycle and a path of order 6 which containing three chords at least such that all of them are independent.

[1,2]-factor;minimal degree; cycle

2016-03-21

山西大學(xué)商務(wù)學(xué)院科研基金項(xiàng)目(2014030).

魯富榮(1981-),男,山西河曲人,碩士,山西大學(xué)商務(wù)學(xué)院基礎(chǔ)教學(xué)部講師，主要從事圖論及其應(yīng)用、復(fù)雜網(wǎng)絡(luò)研究．

1672-2027(2016)02-0012-02

O157.5

A