一類冠圖的2種度結合邊重構數

黃陳辰，　馬美杰

(浙江師范大學 數理與信息工程學院,浙江 金華　321004)

?

一類冠圖的2種度結合邊重構數

黃陳辰，馬美杰

(浙江師范大學 數理與信息工程學院,浙江 金華321004)

根據冠圖Pn5Cm的結構特點,通過分析Pn5Cm的一個度結合邊主子圖可能重構的圖的結構,確定了它的2種度結合邊重構數,推廣了關于路與圈的冠圖的相關結論.

冠圖;邊主子圖;邊重構數;度結合邊重構數

0　引　言

圖的重構猜想最早是由Ulam[1]和Kelly[2-3]提出的.對于圖G,把刪除圖的一個頂點u及與該頂點關聯的邊后得到的子圖稱為主子圖,記為G-u.由圖的所有主子圖組成的多重集合稱為主子圖集.圖的重構猜想是指每個至少有3個頂點的圖都能唯一地被它的主子圖集所確定.其后,Harary[4]提出了邊重構猜想,即至少含有4條邊的圖能夠被它的邊主子圖集所決定,其中,邊主子圖是指在圖G中刪除一條邊e后得到的子圖,記為G-e.本文主要考慮度結合邊主子圖的重構問題.用d(v)表示圖G中頂點v的度,對圖G的邊e=uv,其邊度為d(e)=d(u)+d(v)-2.圖的度結合邊主子圖由邊主子圖和刪除邊的邊度組成,記為(G-e,d(e)).度結合邊重構數是指能重構圖G所需的度結合邊主子圖的最少個數,記為dern(G).一致度結合邊重構數是指任意k個度結合邊主子圖都能重構圖G的最小整數k,記為adern(G).

關于圖的重構已經有了一些結論.1995年,劉富貴[5]證明了關于重構猜想的部分結果;2003年,劉桂真等[6]給出了兩類圖同構的充分必要條件;2007年,謝力同等[7]討論了連通圖的可重構性;2012年,Monikandan等[8]確定了當圖G為正則圖、完全二部圖、路、輪圖、雙星圖或平衡三部圖時,dern(G)和adern(G)的值.

G1和G2的冠圖,是指G1的一個拷貝和G2的|V(G1)|個拷貝,且G1的第i個頂點與G2的第i個拷貝的每個頂點均相連,記為G15G2.2013年,Monikandan等[9]確定了Cn5Km和Pn5K1的2種度結合邊重構數;2015年,石黃萍等[10]給出了冠圖P25Cm的2種度結合邊重構數.

記Δ(G)為G的最大度,δ(G)為G的最小度;用Pn(n≥1)表示n階路;Cm(m≥3)表示m階圈;Kn(n≥1)表示n階完全圖.輪圖是指在一個n-1(n≥4)階圈中加一個點,使得該點與圈上的每個點均有邊相連,記為Wn(n≥4).記Pn5Cm(n≥1,m≥3)表示Pn和Cm的冠圖.由冠圖的定義知,δ(Pn5Cm)=3,P15Cm?Wm+1.

1　預備知識

引理1[8]若Wn是n(n≥4)階的輪圖,則dern(Wn)=1,且

引理2[10]令G=P25Cm.若m≥3,則

引理3[10]若圖G有一條邊e滿足:d(e)=0或者在G-e中除邊e的端點之外的任意2個不相鄰點的度和不等于d(e),則度結合邊主子圖(G-e,d(e))可重構圖G.

引理4令G=Pn5Cm(n≥1,m≥3),則G中的度結合圈邊主子圖(G-e,4)可重構圖G.

證明在G中取Cm中的一條邊e,其度結合邊主子圖為(G-e,4).在G-e中,由m≥3知,除邊e的2個端點外,任意2個不相鄰點的度和至少為5.由引理3知,(G-e,4)可重構圖G.引理4證畢.

引理5令G=Pn5Cm(n≥4,m≥3),則G的2個不同的度結合路邊主子圖可重構圖G.

證明設圖G的2個度結合路邊主子圖為(G-hk,2m+2)和(G-hl,d(hl)).圖H′表示在邊主子圖G-hk中添加一條2m+2度邊e′后得到的圖.當n=4時,邊主子圖G-hk中恰有4個最大度為m+1的點,連接任2個不相鄰的m+1度點后得到的圖H′，都有H′?G.下設n≥5.

1)邊e′的2個端點的點度都是m+1.

若H′G,則邊e′的2個端點在G-hk的同一分支中,且邊e′在圖H′的一個圈C上.圈C上的邊度都是2m+2,且刪除圈C上任一條邊后得到的邊主子圖與G-hk同構.

當n=5時,圖H′的不在圈C上的邊度都小于2m+1,故圖H′的度結合邊主子圖集不含(G-hl,d(hl)).

當n≥6時,在圖H′中刪除不在圈C上的2m+2或2m+1度邊后得到的邊主子圖有3個連通分支,而G-hl只有2個連通分支,故圖H′的邊主子圖集不含G-hl.

2)邊e′的2個端點的點度不同,即m=3,d(e′)=8且邊e′的2個端點u和v在G-hk中的點度分別為3和5,因此dH′(v)=6.因為Δ(G)=5,所以圖H′中不與點v關聯邊的邊主子圖不在圖G的邊主子圖集中.圖H′中與點v關聯的7度邊e"的另一端點的點度為3,邊主子圖H′-e"的最小度為2,而圖G的7度邊的邊主子圖的最小度為3,故圖H′的邊主子圖集不含G-h1.若圖H′中除邊e′外,與點v關聯邊的邊度都不等于8,則圖H′的邊主子圖集不含G-hl;若圖H′中除邊e′外,與點v關聯邊h′的邊度為8,則點v是圖G的邊h1的端點;若邊e′的另一端點u與h1的異于v的端點相鄰,則H′-h′?G-hk.否則,邊主子圖H′-h′有個K4分支,而G-hl(l≠1)沒有此分支,所以圖H′的邊主子圖集不含G-hl.

綜上即可得引理5的結論.證畢.

引理6令G=Pn5Cm(n≥2,m≥3),則G的一個度結合路邊主子圖和一個度結合交叉邊主子圖可重構圖G.

證明設圖G的一個度結合路邊主子圖為(G-hk,d(hk)),另一個度結合交叉邊主子圖為(G-ei,d(ei)).圖H′表示在邊主子圖G-hk中添加一條d(hk)度邊e′后得到的圖.若邊e′的2個端點在G-hk的同一分支中,則圖H′含有2個連通分支,而邊主子圖G-ei都是連通圖.所以,圖H′的邊主子圖集不含G-ei.下設邊e′的2個端點為u和v，并使u和v在G-hk的不同分支中.若邊e′的一個端點u在G-hk中的點度為m+2,則dH′(u)=m+3.因為Δ(G)=m+2,所以圖H′中不與點u相關聯的邊的邊主子圖不在圖G的邊主子圖集中.在H′中與點u相關聯的邊的邊度至少為m+4,而ei的邊度至多為m+3,所以圖H′的邊主子圖集不含G-ei.因此,邊e′的端點在G-hk中的點度至多為m+1.

當d(hk)=2m+2時,邊e′的2個端點在G-hk中的點度均為m+1,則H′?G.

當d(hk)=2m+1時,邊hk為h1,邊e′的2個端點在G-h1中的點度分別為m和m+1,則H′?G.

當d(hk)=2m時,n=2且只有一條路邊.當m=3時,G-hk中所有的頂點都是3度點,任意連接2個不相鄰的3度點后得到圖H′,有H′?G;當m≥4時,G-hk中除邊hk的2個端點外,任何2個不相鄰點的度和不等于2m.由引理3知,(G-hk,2m)可重構圖G.

引理6證畢.

引理7令G=Pn5Cm(n≥3,m≥3),則G的2個度結合交叉邊主子圖可重構圖G.

證明設G的2個度結合交叉邊主子圖為(G-ei,d(ei))和(G-ej,d(ej)),且d(ei)≥d(ej).圖H′表示在邊主子圖G-ei中添加一條d(ei)度邊e′后得到的圖.

1)d(ei)=m+3.若H′G,且e′的2個端點在圖G-ei的度分別為為m+1和2,則H′至多有n-2條割邊.在H′中刪除m+3或m+2度邊e"后得到的邊主子圖H′-e"仍至多有n-2條割邊,而G-ej有n-1條割邊.因此,圖H′的邊主子圖集不含G-ej.

若H′G,且e′的2個端點在圖G-ei的度均為3,則m=3且e′的2個端點在圖G-ei的不同圈C3中.設e′的2個端點如圖1所示.圖H′中有n-2條割邊.在H′中刪除6度邊e"后得到的圖H′-e"有n-1條割邊,但此時H′-e"的直徑為n+2,而G-ej的直徑為n+1.否則,在H′中刪除不同于e′的5或6度邊后得到的邊主子圖至多有n-2條割邊,而G-ej有n-1條割邊.因此,圖H′的邊主子圖集不含G-ej.

圖1　邊e′的2個端點均為3度點的重構圖H′(H′G)

2)d(ei)=m+2,即2個度結合交叉邊主子圖都為(G-e1,m+2).當m≥5時,由m+2≥7和引理3知,H′?G.下設3≤m≤4.若H′G且e′的2個端點在圖G-e1的不同圈Cm中,則H′至多有n-2條割邊.從H′中刪除m+2度邊e"后H′-e"仍至多有n-2條割邊,而G-e1有n-1條割邊,故圖H′的邊主子圖集不含2個G-e1.

若H′G且e′的2個端點在圖G-e1的同一圈Cm中,則m=4且H′有3個4度點.而G-e1只有1個4度點.故刪除的6度邊e"的2個端點都為4度點,即只需考慮e′的端點在圖G的同一C4圈中且e1的一個端點在該圈上的情況.刪去e"后,在H′-e"中無4度點與6度點相鄰,而在G-e1中有1個4度點與6度點相鄰.故圖H′的邊主子圖集不含2個G-e1.

綜上即可得引理7的結論.證畢.

2　主要結果

根據引理4的證明,可得如下定理:

定理1令G=Pn5Cm(n≥1,m≥3),則dern(G)=1.

定理2令G=Pn5Cm.若n≥1和m≥3,則

證明當n∈{1,2}時,由引理1和引理2可知結論成立.下設n≥3.由引理4～引理7知,圖G的任意3個度結合邊主子圖集S可重構圖G,所以adern(G)≤3.

當n∈{3,4},m≥4時,圖G的任意2個度結合邊主子圖集可重構圖G.由引理4～引理7知,只需證明圖G的2個度結合邊主子圖(G-h1,2m+1)可重構圖G.圖H′表示在邊主子圖G-h1中添加一條2m+1度邊e′后得到的圖.當m≥5或m=4,n=3時,邊e′的端點是G-h1中2個不相鄰的m和m+1度點,有H′?G.當m=4,n=4時,若H′G,則此時Δ(H′)=7,不妨設d(v)=Δ(H′)=7.由于Δ(G)=6,且在H′中與頂點v相關聯的邊中只有一條為2m+1度邊,所以圖H′的邊主子圖集不含2個度結合邊主子圖(G-h1,2m+1).因此,adern(G)≤2.

下面證明下界.

1)m=3.當n=3時,圖2所示的圖與P35Cm有2個公共的度結合邊主子圖(G-h1,7),所以,adern(G)≥3.當n=4時,圖3所示的圖與P45Cm有2個公共的度結合邊主子圖(G-h1,7),所以,adern(G)≥3.

n=3　　　　　　　　　　　　　　　　　　　　　　　n=4圖2　含2個(G-h1,7)的重構圖H′(H′G)　　　圖3　含2個(G-h1,7)的重構圖H′(H′G)

2)當n∈{3,4},m≥4時,圖5所示的圖與圖G有1個公共的度結合邊主子圖(G-e2,m+3),所以,adern(G)≥2.

綜上,即可得定理2的結論.證畢.

圖4　含2個(G-hi,2m+2)的重構圖H′(H′G)

圖5　含1個(G-e2,m+3)的重構圖H′(H′G)

3　結　語

本文通過分析冠圖Pn5Cm的結構特點,尋找一個圖,使其與冠圖有盡可能多的公共的度結合邊主子圖,從而確定它的下界,由下界猜測其上界,并加以證明,確定了冠圖Pn5Cm的2種度結合邊重構數.結合其他學者已經得到的關于冠圖的度結合邊重構數的結論,還可以考慮關于冠圖G=Cn5Pm與G=Pn5Pm的2種度結合邊重構數.

[1]UlamSM.Acollectionofmathematicalproblems[M].NewYork:IntersciencePublishers,1960:20.

[2]KellyPJ.Onisometrictransformations[D].Wisconsin:UniversityofWisconsin-Madison,1942.

[3]KellyPJ.Acongruencetheoremfortrees[J].PacificJMath,1957,7(1):961-968.

[4]HararyF.Onthereconstructionofagraphfromacollectionofsubgraphs[C]//FielderM.Theoryofgraphsanditsapplications.NewYork:AcademicPress,1964:47-52.

[5]劉富貴.關于重構猜想的部分結果[J].武漢交通科技大學學報,1995,19(1):66-68.

[6]劉桂真,禹繼國,謝力同.兩類圖同構的充分必要條件[J].山東大學學報:自然科學版,2003,38(3):1-4.

[7]謝力同,劉家壯.論連通圖的可重構性[J].經濟數學,2007,24(3):221-223.

[8]MonikandanS,RajSS.Degreeassociatededgereconstructionnumber[J].CombinatorialAlgorithms,2012,7643(3):100-109.

[9]MonikandanS,AnushaDP,SundarRS.Degreeassociatededgereconstructionnumberofgraphs[J].JDiscreteAlgorithms,2013,23(1):35-41.

[10]石黃萍,馬美杰.冠圖P25Cm的2種度結合邊重構數[J].浙江師范大學學報:自然科學版,2015,38(2):176-178.

(責任編輯陶立方)

Two degree associated edge reconstruction numbers of a kind of corona graph

HUANG Chenchen,MA Meijie

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

Based on the structure property of the corona graphPn5Cm, it was determined the two degree associated edge reconstruction numbers ofPn5Cmby considering the possible reconstructions from a degree-associate edge-card. The results extended some relevant results about the corona graph of path and cycle.

corona graph; edge-card; edge reconstruction number; degree-associate edge reconstruction number

10.16218/j.issn.1001-5051.2016.03.005

收文日期：2015-10-17；2015-12-11

黃陳辰(1990-),女,浙江海寧人,碩士研究生.研究方向:圖論.

馬美杰.E-mail: mameij@zjnu.cn

O157.5

A

1001-5051(2016)03-0263-05