冠圖P3·Cm的兩種度結合邊重構數

黃陳辰，石黃萍

（浙江師范大學 數理與信息工程學院，浙江金華321004）

冠圖P3·Cm的兩種度結合邊重構數

黃陳辰，石黃萍

（浙江師范大學 數理與信息工程學院，浙江金華321004）

摘要：邊重構猜想是指至少含有邊的圖能被它的邊主子圖集所決定,通過分析冠圖的一個邊主子圖可能重構的圖的結構,確定了它的兩種邊度結合重構數,進一步豐富了結構圖論的內容.

關鍵詞：冠圖;重構;邊主子圖;度結合邊重構數

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)為G的最大度，δ(G)為G的最小度，對于圖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等確定了當圖G為正則圖、完全二部圖、路、輪圖、雙星圖或平衡三部圖時，這兩種度結合邊重構數的值［5］.2011年，田京京研究了某些廣義冠圖的強邊染色［6］;2013年，Monikandan等確定了Cn·Km和Pn·K1的兩種度結合邊重構數［7］.本文是在這些結論的基礎上繼續研究冠圖的兩種邊度結合重構數.

1　相關引理

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

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

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

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

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

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

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

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

2　主要結果

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

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

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

情況1m+3.

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

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

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

因此，adern(G)=3.

情況2m≥4.

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

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

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

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

3　結語

本文通過分析冠圖P3·Cm的一個邊主子圖可能重構的圖的結構,確定了它的兩種邊度結合重構數,結論分別為:當m≥4時,adern(G)=2,當m=3時，adern(G)=3.對于一般的冠圖Pn·Cm,由于邊主子圖集里的邊主子圖是多樣的,重構過程很復雜,未來可進一步確定它的兩種邊度結合重構數.

參考文獻:

［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］劉桂真,禹繼國,謝力同.兩類圖同構的充分必要條件［J］.山東大學學報:理學版,2003,3(1):1-4.

［4］杜鵑,呂嘉鈞.有向路的重構［J］.南通大學學報:自然科學版,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］田京京.若干圈的廣義冠圖的-強邊染色［J］.數學雜志,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.

（責任編輯：邵曉軍）

中圖分類號：O157.5

文獻標識碼：A

文章編號：1007-5348（2015）06-0005-03

［收稿日期］2014-11-06

［基金項目］國家自然科學基金項目（11101378）.

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

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