石黃萍， 馬美杰

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

冠圖P25Cm的2種度結(jié)合邊重構(gòu)數(shù)*1

石黃萍， 馬美杰

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

通過分析冠圖P5C的一個(gè)邊主子圖可能重構(gòu)的圖的結(jié)構(gòu),確定了它的2種邊度結(jié)合重構(gòu)數(shù),進(jìn)一步豐富了結(jié)構(gòu)圖論的內(nèi)容.

冠圖;重構(gòu);邊主子圖;度結(jié)合邊重構(gòu)數(shù)

0 引 言

Ulam猜想[1]的內(nèi)容就是:若圖G和H分別是包含n個(gè)頂點(diǎn)ui和vi的圖(n≥3),對(duì)于所有的i,都有G-ui同構(gòu)于H-vi,則G和H同構(gòu).Ulam猜想吸引許多學(xué)者對(duì)其進(jìn)行深入研究.其后,Harary[2]提出了邊重構(gòu)猜想,即至少含4條邊的圖能夠被它的邊主子圖集所決定.其中,邊主子圖是指在圖G中刪除一條邊e后所得到的子圖,記為G-e.本文主要考慮度結(jié)合邊主子圖的重構(gòu)問題.用d(v)表示圖G中頂點(diǎn)v的度,對(duì)圖G的邊e=uv,其邊度為d(e)=d(u)+d(v)-2.度結(jié)合邊主子圖是指由邊主子圖和被刪除邊的邊度組成,記為(G-e,d(e)).度結(jié)合邊重構(gòu)數(shù)是指能重構(gòu)圖G所需的度結(jié)合邊主子圖的最少個(gè)數(shù),記為dern(G).一致度結(jié)合邊重構(gòu)數(shù)是指任意k個(gè)度結(jié)合邊主子圖都能重構(gòu)圖G的最小整數(shù)k,記為adern(G).

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

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

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

1 主要結(jié)果

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

證明 考慮在邊主子圖G-e中添加一條邊度為d(e)的邊e′的重構(gòu)圖.若d(e)=0,則邊e′的2個(gè)端點(diǎn)在邊主子圖G-e中的度都為0,即邊e′是連接G-e中的2個(gè)孤立點(diǎn),故產(chǎn)生的圖與G同構(gòu).對(duì)于另一種情況,考慮G-e中不相鄰的2個(gè)頂點(diǎn)的度和,因?yàn)橹挥羞卐的2個(gè)端點(diǎn)的度和為d(e),故邊e′的2個(gè)端點(diǎn)只能是邊e的2個(gè)端點(diǎn),從而獲得的圖也同構(gòu)于G.引理1證畢.

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

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

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

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

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

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

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

故下面考慮邊度為m+2的度結(jié)合邊主子圖的重構(gòu).

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

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

圖1 與圖G有公共度結(jié)合邊主子圖的重構(gòu)圖

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

2 結(jié) 語

本文通過分析冠圖P25Cm的一個(gè)邊主子圖可能重構(gòu)的圖的結(jié)構(gòu),確定了它的2種邊度結(jié)合重構(gòu)數(shù).對(duì)于一般的冠圖Pn5Cm,筆者將進(jìn)一步確定它的2種邊度結(jié)合重構(gòu)數(shù).

[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]劉桂真,禹繼國(guó),謝力同.兩類圖同構(gòu)的充分必要條件[J].山東大學(xué)學(xué)報(bào):理學(xué)版,2003,3(1):1-4.

[4]杜鵑,呂嘉鈞.有向路的重構(gòu)[J].南通大學(xué)學(xué)報(bào):自然科學(xué)版,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-強(qiáng)邊染色[J].數(shù)學(xué)雜志,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.

(責(zé)任編輯 陶立方)

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

國(guó)家自然科學(xué)基金項(xiàng)目資助(11101378)

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

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

O157.5

A

1001-5051(2015)02-0176-03