冠圖P25Cm的2種度結合邊重構數*1

石黃萍， 馬美杰

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

冠圖P25Cm的2種度結合邊重構數*1

石黃萍， 馬美杰

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

通過分析冠圖P5C的一個邊主子圖可能重構的圖的結構,確定了它的2種邊度結合重構數,進一步豐富了結構圖論的內容.

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

0 引 言

Ulam猜想[1]的內容就是:若圖G和H分別是包含n個頂點ui和vi的圖(n≥3),對于所有的i,都有G-ui同構于H-vi,則G和H同構.Ulam猜想吸引許多學者對其進行深入研究.其后,Harary[2]提出了邊重構猜想,即至少含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).

關于圖的重構已經有了一些結論.2003年,劉桂真等[3]給出了兩類圖同構的充分必要條件;2006年,杜鵑等[4]研究了有向路的重構;2012年,Monikandan等[5]確定了當圖G為正則圖、完全二部圖、路、輪圖、雙星圖或平衡三部圖時,dern(G)和adern(G)的值.

G1和G2的冠圖,是指G1的一個拷貝和G2的|V(G1)|個拷貝,且G1的第i個頂點與G2的第i個拷貝的每個頂點均相連,記為G15G2.2011年,田京京[6]研究了某些廣義冠圖的強邊染色;2013年,Monikandan等[7]確定了Cn5Km和Pn5K1的2種度結合邊重構數.

記Δ(G)為G的最大度,δ(G)為G的最小度;用Pn(n≥1)表示n階路;Cm(m≥3)表示m階圈.記Pn5Cm為Pn和Cm的冠圖.

1 主要結果

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

證明 考慮在邊主子圖G-e中添加一條邊度為d(e)的邊e′的重構圖.若d(e)=0,則邊e′的2個端點在邊主子圖G-e中的度都為0,即邊e′是連接G-e中的2個孤立點,故產生的圖與G同構.對于另一種情況,考慮G-e中不相鄰的2個頂點的度和,因為只有邊e的2個端點的度和為d(e),故邊e′的2個端點只能是邊e的2個端點,從而獲得的圖也同構于G.引理1證畢.

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

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

由定理1的證明可以得到如下推論:

推論1令G=P25Cm(m≥3),則G的邊度為4的度結合邊主子圖(G-e,4)可重構圖G.

定理2令G=P25Cm,若m≥3,則

證明 圖G中的度結合邊主子圖只有3種情況,分別為:(G-e1,4),(G-e2,m+2),(G-e3,2m).則它們的邊度分別為4,m+2,2m.由推論1知,邊度為4的度結合邊主子圖(G-e1,4)可重構圖G.

下證度結合邊主子圖(G-e3,2m)可重構圖G.令H′表示可由(G-e3,2m)重構的圖,即在邊主子圖G-e3中添加一條2m度邊e′.當m=3時,G-e3中所有的頂點都是3度點,任意連接2個不相鄰的3度點得到圖H′, 有H′?G.當m≥ 4時,在邊主子圖G-e3中除邊e3的2個端點外,任何2個不相鄰點的度和不等于d(e3).由引理1知,該邊主子圖可重構圖G.

故下面考慮邊度為m+2的度結合邊主子圖的重構.

當m=3時,只須證明3個度結合邊主子圖(G-e2,5)可重構圖G.由圖G-e2的結構知,圖G-e2恰有一條割邊.圖H′表示在邊主子圖G-e2中添加一條5度邊e′得到的圖.若H′G,則在H′中只有在2條5度邊刪除后才有割邊,故H′至多含有2個(G-e2,5).因此,adern(G)≤3.由圖1(a)與圖G有2個相同的公共度結合邊主子圖(G-e2,5)可知,adern(G)≥3.

當m=4時,只須證明2個度結合邊主子圖(G-e2,6)可重構圖G.由于邊主子圖Δ(G-e2)=5且只有一個最大度點,不妨設d(v)=Δ(G-e2)=5,則v在G-e2中有一個4度鄰點.圖H′表示在邊主子圖G-e2中添加一條6度邊e′得到的圖.若H′G,則圖H′只含一個最大度點v且d(v)=5.若在圖H′中刪除不同于e′的6度邊e"后得到邊主子圖G-e2,則邊e"與點v不關聯.若e′的端點分別在圖G的2個Cm圈中,則此時H′無割邊,且在圖H′中刪除不同于邊e′的6度邊e"后得到的圖都不含割邊.而在邊主子圖G-e2中有一條割邊.若e′的端點在圖G的同一Cm圈中且e2的端點不在該圈上,則圖H′中的6度邊都與點v關聯.若e′的端點在圖G的同一Cm圈中且e2的一個端點在該圈上,則在H′-e"中與v相鄰的點均為3度點,而在G-e2中與v相鄰的點有一個4度點.故圖H′的邊主子圖集不含2個邊主子圖G-e2.因此,adern(G)≤2.由圖1(b)與圖G有一個公共的度結合邊主子圖(G-e2,6)知,adern(G)≥2.

圖1 與圖G有公共度結合邊主子圖的重構圖

當m≥5時,在邊主子圖G-e2中,由于m+2≥7,所以除去邊e2的2個端點外,任何2個不相鄰點的度和不等于m+2.由引理1知,該邊主子圖可重構圖G.因此,adern(G)=1.定理2證畢.

2 結 語

本文通過分析冠圖P25Cm的一個邊主子圖可能重構的圖的結構,確定了它的2種邊度結合重構數.對于一般的冠圖Pn5Cm,筆者將進一步確定它的2種邊度結合重構數.

[1]Ulam S M.A collection of mathematical problems[M].New York:Interscience Publishers,1960:20.

[2]Harary F.On the reconstruction of a graph from a collection of subgraphs[C]//Fielder M.Theory of Graphs and its Applications.New York:Academic Press,1964:47-52.

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

[4]杜鵑,呂嘉鈞.有向路的重構[J].南通大學學報:自然科學版,2006,5(1):1517.

[5]Monikandan S,Anusha Devi P,Sundar Raj S.Degree associated edge reconstruction number[J].Combinatorial Algorithms,2012,7643(3):100-109.

[6]田京京.若干圈的廣義冠圖的2-強邊染色[J].數學雜志,2011,31(5):938-944.

[7]Monikandan S,Anusha Devi P,Sundar Raj S.Degree associated edge reconstruction number of graphs[J].J Discrete Algorithms,2013,23(2):35-41.

(責任編輯 陶立方)

TwokindsofdegreeassociatededgereconstructionnumbersofcoronagraphP25Cm

SHI Huangping, MA Meijie

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

Two kinds of degree associated edge reconstruction numbers of the graphP25Cmwere determined by considering the possible reconstructions from a degree-associate edge-card. The results enriched the structure property of graphs.

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

10.16218/j.issn.1001-5051.2015.02.09

2014-11-03

國家自然科學基金項目資助(11101378)

石黃萍(1990-),女,江西上饒人,碩士研究生.研究方向:圖論.

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

O157.5

A

1001-5051(2015)02-0176-03