黃陳辰，石黃萍

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

冠圖P3·Cm的兩種度結(jié)合邊重構(gòu)數(shù)

黃陳辰，石黃萍

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

摘要：邊重構(gòu)猜想是指至少含有邊的圖能被它的邊主子圖集所決定,通過(guò)分析冠圖的一個(gè)邊主子圖可能重構(gòu)的圖的結(jié)構(gòu),確定了它的兩種邊度結(jié)合重構(gòu)數(shù),進(jìn)一步豐富了結(jié)構(gòu)圖論的內(nèi)容.

關(guān)鍵詞：冠圖;重構(gòu);邊主子圖;度結(jié)合邊重構(gòu)數(shù)

Ulam猜想［1］:如果圖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提出了邊重構(gòu)猜想［2］，即至少含4條邊的圖能夠被它的邊主子圖集所決定，其中，邊主子圖是指在圖G中刪除一條邊e后所得到的子圖，記為G-e.用d(v)表示圖G中頂點(diǎn)v的度，記△(G)為G的最大度，δ(G)為G的最小度，對(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).本文主要考慮度結(jié)合邊主子圖的邊重構(gòu)問(wèn)題，以進(jìn)一步豐富結(jié)構(gòu)圖論的內(nèi)容.

關(guān)于圖的重構(gòu)已經(jīng)有了一些重要的結(jié)論.2003年，劉桂真等給出了兩類(lèi)圖同構(gòu)的一個(gè)充分必要條件［3］; 2006年，杜鵑等研究了有向路的重構(gòu)［4］；2012年，Monikandan等確定了當(dāng)圖G為正則圖、完全二部圖、路、輪圖、雙星圖或平衡三部圖時(shí)，這兩種度結(jié)合邊重構(gòu)數(shù)的值［5］.2011年，田京京研究了某些廣義冠圖的強(qiáng)邊染色［6］;2013年，Monikandan等確定了Cn·Km和Pn·K1的兩種度結(jié)合邊重構(gòu)數(shù)［7］.本文是在這些結(jié)論的基礎(chǔ)上繼續(xù)研究冠圖的兩種邊度結(jié)合重構(gòu)數(shù).

1　相關(guān)引理

G1和G2的冠圖，是指G1的一個(gè)拷貝和G2的|V(G1)|個(gè)拷貝，且G1的第i個(gè)頂點(diǎn)與G2的第i個(gè)拷貝的每個(gè)頂點(diǎn)均相連，記為G1·G2.本文研究的是冠圖P3·Cm，其中P3是指3個(gè)頂點(diǎn)的路，Cm是指m個(gè)頂點(diǎn)的圈.

引理1若圖G有一條邊e滿(mǎn)足:d(e)=0或者在G-e中除e的端點(diǎn)之外的任何兩個(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.證畢.

引理2令G=P3·Cm(m≥3)，則G的度結(jié)合邊主子圖(G-e,2m+1)可重構(gòu)圖G.

證圖H表示在邊主子圖G-e中添加一條2m+1度邊e得到的圖.因?yàn)?m+1≥9，邊e的端點(diǎn)只能是G-e中2個(gè)不相鄰的m和m+1度點(diǎn)，由引理1知，H?G.

引理3令G=P3·Cm(m≥3)，則G的任意兩個(gè)不同的度結(jié)合邊主子圖S可重構(gòu)圖G.

證令H表示可由S重構(gòu)的圖.若S包含邊度為4的度結(jié)合邊主子圖(S-e,4)，則由引理1知，H?G.下面考慮S不包含邊度為4的度結(jié)合邊主子圖.圖G中不等于4的邊度可能情況為:m+2,m+3,2m+1.記其度結(jié)合邊主子圖分別為(G-e1,m+2)，(G-e2,m+3)，(G-e3,2m+1).

若(G-e3,2m+1)∈S，圖H表示在邊主子圖G-e3中添加一條2m+1度邊e得到的圖.當(dāng)m≥4時(shí)，由引理2知，有H?G.當(dāng)m=3時(shí)，若H?G，此時(shí)邊e的2個(gè)端點(diǎn)在G-e3的同一分支K中，即H含有2個(gè)連通分支.而邊主子圖G-e1，G-e2都是連通圖.因此圖H的邊主子圖集不含G-ej(j∈{1,2}).即集合S可重構(gòu)圖G.

下設(shè)S={(G-e1,m+2),(G-e2,m+3)}，圖H表示在邊主子圖G-e2中添加一條m+3度邊e,得到的圖.若H?G，因?yàn)閙≥3，邊e的2個(gè)端點(diǎn)分別在路P3和某個(gè)圈Cm上，且m=3時(shí)，邊e的2個(gè)端點(diǎn)還可能在2個(gè)Cm圈上，但重構(gòu)圖H都至多有1條割邊，從H中刪除m+2度邊后的圖仍至多有1條割邊，而邊主子圖G-e2有2條割邊，故圖H的邊主子圖集不含G-e1.因此集合S可重構(gòu)圖G.證畢.

2　主要結(jié)果

定理1令G=P3·Cm(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令G=P3·Cm(m≥3)，則G的度結(jié)合邊主子圖(G-e,4)可重構(gòu)圖G.

定理2令G=P3·Cm(m≥3)，則：

證由推論1知，度結(jié)合邊主子圖(G-e,4)可重構(gòu)圖G.由引理3知，任意2個(gè)不同的度結(jié)合邊主子圖可重構(gòu)圖G，故下面只考慮度結(jié)合邊主子圖集S含有相同的且邊度大于4的度結(jié)合邊主子圖.圖G中不等于4的邊度的可能情況分別為:m+2,m+3,2m+1.記其度結(jié)合邊主子圖分別為(G-e1,m+2)，(G-e2,m+3)，(G-e3,2m+1).

情況1m+3.

由圖1中的重構(gòu)圖與圖G有2個(gè)公共的度結(jié)合邊主子圖(G-e3,7)可知，adern(G)≥3.下面證圖G的任何3個(gè)相同的度結(jié)合邊主子圖集S都能重構(gòu)圖G.

若(G-e2,6)∈S，則圖H表示在邊主子圖G-e2中添加一條6度邊e得到的圖.若H?G且e的端點(diǎn)在圖H-e的不同Cm圈中，則此時(shí)H中只有1條不同于e的6度邊e″滿(mǎn)足刪除它后有2條割邊，但H-e″的直徑至少為5，而G-e2的直徑為4.若H?G且e的端點(diǎn)分別在圖G-e3的路P3和某個(gè)Cm圈中，則此時(shí)H只有1條割邊，H-e″仍只有1條割邊，而G-e2有2條割邊.故若H?G時(shí)，它的邊主子圖集不含2個(gè)度結(jié)合邊主子圖(G-e2,6).

若(G-e1,5)∈S，圖H表示在邊主子圖G-e1中添加1條5度邊e得到的圖.若H?G，則此時(shí)H至多有1條割邊，令e″表示不同于e的5度邊，則H-e″仍至多有1條割邊，而G-e1有2條割邊.故若H?G時(shí)，它的邊主子圖集不含2個(gè)度結(jié)合邊主子圖(G-e1,5).

因此，adern(G)=3.

情況2m≥4.

由引理1知，adern(G)≥2.只要證明圖G的任何2個(gè)相同的度結(jié)合邊主子圖集S都能重構(gòu)圖G即可.由引理2知，S不包含度結(jié)合邊主子圖(G-e3,2m+1).

若(G-e2,m+3)∈S，圖H表示在邊主子圖G-e2中添加一條m+3度邊e得到的圖.因?yàn)閙+3≥7，所以若H?G，則e的2個(gè)端點(diǎn)分別在路P3和某個(gè)Cm上.此時(shí)H至多有1條割邊，從中刪除不同于e的m+3度邊e″后仍至多有1條割邊，而G-e3有2條割邊.故若H?G,時(shí)，它的邊主子圖集不含2個(gè)度結(jié)合邊主子圖(G-e2,m+3).

若(G-e1,m+2)∈S，圖H表示在邊主子圖G-e1中添加一條m+2度邊e得到的圖.當(dāng)m≥5時(shí)，由m+ 2≥7和引理1可知有H?G.當(dāng)m=4時(shí)，若H?G且e的2個(gè)端點(diǎn)在不同C4圈中，則此時(shí)H至多有1條割邊，從中刪除不同于e的6度邊e″后仍至多有1條割邊，而G-e1有2條割邊.若H?G且e的2個(gè)端點(diǎn)在同一圈C4中，則H有3個(gè)4度點(diǎn)，而G-e1只有一個(gè)4度點(diǎn).故刪除不同于e的6度邊e″的2個(gè)端點(diǎn)都為4度點(diǎn).所以在H-e″中無(wú)4度點(diǎn)與6度點(diǎn)相鄰，而在G-e1中一個(gè)4度點(diǎn)與6度點(diǎn)相鄰.故若H?G時(shí)，它的邊主子圖集不含2個(gè)度結(jié)合邊主子圖(G-e1,m+2).

因此adern(G)=2.證畢.

3　結(jié)語(yǔ)

本文通過(guò)分析冠圖P3·Cm的一個(gè)邊主子圖可能重構(gòu)的圖的結(jié)構(gòu),確定了它的兩種邊度結(jié)合重構(gòu)數(shù),結(jié)論分別為:當(dāng)m≥4時(shí),adern(G)=2,當(dāng)m=3時(shí)，adern(G)=3.對(duì)于一般的冠圖Pn·Cm,由于邊主子圖集里的邊主子圖是多樣的,重構(gòu)過(guò)程很復(fù)雜,未來(lái)可進(jìn)一步確定它的兩種邊度結(jié)合重構(gòu)數(shù).

參考文獻(xiàn):

［1］Ulam S M.A collection of mathematical problems［M］.New York-London：Interscience Publishers，1960:20.

［2］Harary F.On the reconstruction of a graph from a collection of subgraphs［M］.Prague：Theory of Graphs and its Applications,1964: 47-52.

［3］劉桂真,禹繼國(guó),謝力同.兩類(lèi)圖同構(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):15-17.

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

［6］田京京.若干圈的廣義冠圖的-強(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］.Journal of Discrete Algorithms,2013,23(2):35-41.

（責(zé)任編輯：邵曉軍）

中圖分類(lèi)號(hào)：O157.5

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1007-5348（2015）06-0005-03

［收稿日期］2014-11-06

［基金項(xiàng)目］國(guó)家自然科學(xué)基金項(xiàng)目（11101378）.

［作者簡(jiǎn)介］黃陳辰（1990-），女，浙江海寧人，浙江師范大學(xué)數(shù)理與信息工程學(xué)院碩士研究生；研究方向：圖論.

Two Kinds of Degree-associated Edge Reconstruction Numbers of P3· Cm

HUANG Chen-chen,SHI Huang-ping
（College of Mathematics,Physics and Information Engineering, Zhejiang Normal University,Jinhua 321004,Zhejiang,China）

Abstract:Edge-reconstruction conjecture states that every graph with more than three edges is determined by its edge-card.Two kinds of degree associated edge reconstruction numbers of the graph P3·Cmare determined by considering the possible reconstructions from a degree-associate edge-card.The results enrich the structure property of graphs.

Key words:corona graph;reconstruction;edge-card;degree-associate edge reconstruction number