石黃萍,袁鄧彬,張芬

(上饒師范學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院，江西 上饒 334001)

1 相關(guān)知識

在20世紀中葉，圖的重構(gòu)猜想是由Ulam在文獻[1]和Kelly在文獻[2]中提出并研究，它是指每個至少有3個頂點的圖都能被它的主子圖集所唯一確定，主子圖集是指所有主子圖組成的集合，而在圖G中刪除一個頂點v后得到的子圖稱為主子圖，記為G-v。之后，許多學(xué)者對圖的重構(gòu)問題引起關(guān)注并對其加以研究。在1985年，Plantholt和Harary在文獻[3]中引進了重構(gòu)數(shù)的概念，它是指能夠唯一確定圖G的所需的主子圖的最少數(shù)目。在2000年，Ramachandran在文獻[4]中考慮在重構(gòu)的主子圖中增加了刪除點的度信息(稱為度結(jié)合主子圖，即是指由主子圖和刪除點的度組成，記為(G-v,d(v))，這里，d(v)表示圖G中頂點v的度)，并提出了度結(jié)合重構(gòu)數(shù)的概念，即能重構(gòu)圖G的所需的度結(jié)合主子圖的最少數(shù)目，記為drn(G)。在2012年，Monikandan等人在文獻[5]中介紹了一致度結(jié)合重構(gòu)數(shù)，是指任意k個度結(jié)合主子圖都能重構(gòu)圖G的最小整數(shù)k，記為adrn(G)。本文繼續(xù)對度結(jié)合重構(gòu)數(shù)進行研究，主要確定PnoCm的度結(jié)合重構(gòu)數(shù)和一致度結(jié)合重構(gòu)數(shù)。

關(guān)于圖的重構(gòu)問題，很多學(xué)者已經(jīng)總結(jié)了一些重要的結(jié)論。在2010年，Barrus和West在文獻[6]中確定了k-正則圖的度結(jié)合重構(gòu)數(shù)的上界為min{k+2,n-k-1}，點傳遞圖的度結(jié)合重構(gòu)數(shù)的下界為3以及毛毛蟲的度結(jié)合重構(gòu)數(shù)為2。在2012年，Monikandan等人在文獻[5]確定了完全圖、輪圖、圈、星圖、完全二部圖的一致度結(jié)合重構(gòu)數(shù)。在2015年，石黃萍等人在文獻[7]中確定了完全多部圖和它的補圖以及雙帚圖的兩種度結(jié)合重構(gòu)數(shù)。在2016年，馬美杰等人在文獻[8]中對類星圖進行研究并確定了該圖的兩種度結(jié)合重構(gòu)數(shù)。本文是在這些已有結(jié)論的基礎(chǔ)上深入研究一類冠圖的兩種度結(jié)合重構(gòu)數(shù)。

故只需確定當(dāng)n≥2時，冠圖PnoCm的兩種度結(jié)合重構(gòu)數(shù)。

2 主要結(jié)果

引理2.1令G=PnoCm(n≠2且m≠3)，則圖G的1個度結(jié)合路點主子圖和1個度結(jié)合圈點主子圖可重構(gòu)圖G。

證明：假設(shè)這2個度結(jié)合主子圖分別為(G-uk,d(uk))和(G-vl,3)。當(dāng)d(uk)=m+1時，G-uk=Cm∪(Pn-1oCm)；當(dāng)d(uk)=m+2時，G-uk=Cm∪(Pn1oCm)∪(Pn2oCm)，其中n1+n2=n-1。令圖H表示在路點主子圖G-uk中添加1個度為d(uk)的新點v'得到的且不同構(gòu)于圖G的重構(gòu)圖。由圈點主子圖G-vl是連通圖可知重構(gòu)圖H為連通圖，故新點v'的鄰點必落在路點主子圖的每個連通分支中。

斷言：新點v'與路點主子圖G-uk中的圈分支Cm中的每個點均相鄰。

(反證法)假設(shè)圈分支Cm中至少存在1個點與v'不相鄰，則當(dāng)d(v')=m+1時；圖H中至少存在1個2-度點且v'至少有2個鄰點落在另一連通分支的路點或圈點中，當(dāng)d(v')=m+2時，圖H中至少存在1個2-度點且v'至少有3個鄰點分別落在另兩個連通分支的路點或圈點中，故從圖H中刪除一個3-度點至多有n-2個割邊，但已知的圈主子圖中存在n-1個割邊，矛盾，故假設(shè)不成立。

由v'在路點主子圖G-uk的除Cm外其他連通分支中均只有一個鄰點，若其中一個鄰點為m+2-度點v''，則n≥4且Δ(H)=m+3,但因為Δ(G-vl)=m+2，所以在圖H中刪除的3-度點必與v''相鄰，刪除后的主子圖中v''的度為m+2且有3個鄰點的度數(shù)大于3，但已知的圈點主子圖中m+2-度點均只有2個鄰點的度數(shù)大于3，矛盾；若其中一個鄰點為3-度點v''，則當(dāng)n≠2且m≠3時，重構(gòu)圖H存在n+1個頂點的度大于3，若刪除的3-度點是v''的鄰點時，則得到的主子圖只有1個2-度點，與已知的圈點主子圖G-vl恰有2個2-度點矛盾；若刪除的3-度點不是v''的鄰點時，則得到的主子圖仍存在n+1個頂點的度大于3，與已知的圈點主子圖G-vl只有n個頂點的度大于3，故假設(shè)不成立。

由以上分析可知，重構(gòu)圖H的度結(jié)合主子圖集中不包含度結(jié)合圈點主子圖(G-vl,3)，故引理得證。

引理2.2令G=PnoCm，則圖G的2個不同的度結(jié)合圈點主子圖可重構(gòu)圖G，3個相同的度結(jié)合圈點主子圖可重構(gòu)圖G。

證明：假設(shè)這2個不同的度結(jié)合圈點主子圖分別為(G-vi,3)和(G-vj,3)，其中刪除點vi和vj分別位于圈點類Vi和Vj中；這3個相同的度結(jié)合圈點主子圖均為(G-vi,3)，其中刪除點vi位于圈點類Vi中。令圖H表示在圈點主子圖G-vi中添加1個新點3-度點v'后得到的不同構(gòu)于圖G的重構(gòu)圖。記圖G中與vi相鄰且落在路Pn上的點為ui。

斷言:新點v'至多有1個鄰點落在圈主子圖G-vi的路Pn上。

(反證法)假設(shè)v'至少有2個鄰點落在圈點主子圖的路Pn上，則從圖H中刪除異于v'的3-度點后至多只有n-2條割邊，但已知的圈點主子圖中含有n-1條割邊，矛盾，故假設(shè)不成立。

若新點v'有1個鄰點與G-vi的路Pn上的uk相鄰，其他的2個鄰點{va,vb}落在圈Cm上，下面分2種情形討論va和vb的位置。

情形1 |N(v')∩N(uk)|=2

由此可知，N(v')∩N(uk)={va,vb}，當(dāng)va，vb分別為G-vi中的2-度點和3-度點，此時ui和uk是同一點，則圖H與G至多有2個相同的(G-vi,3)；當(dāng)va，vb均為G-vi中有公共鄰點的3-度點時，則圖H與G有2個相同的(G-vi,3)；當(dāng)va，vb均為G-vi中無公共鄰點的3-度點時，則圖H中增加2個4-度點，從中刪除異于v'的3-度點比已知的圈主子圖至少增加1個4-度點，故情形1不成立。

情形2 |N(v')∩N(uk)|≤1

從重構(gòu)圖H刪除異于v'的3-度點后至多只有n-2條割邊，但已知的圈主子圖含有n-1條割邊，故情形2不成立。

若v'的3個鄰點全落在G-vi的圈Cm上，則當(dāng)落在不同的圈上時，從圖H中刪除異于v'的3-度點的主子圖至多只有n-2條割邊，但已知的圈主子圖含有n-1條割邊；當(dāng)落在同一圈上時，若該圈原為vi點所在的圈，則刪除異于v'的3-度點后的主子圖比已知的圈主子圖中的m+1-度點相差1個；若該圈不為vi點所在的圈，則刪除3-度點后的圖比已知的圈主子圖中的4+-度點至少增加1個，故此情況不成立。

由以上分析，引理得證。

引理2.3令G=PnoCm(m≥4)，若n∈{3,4}，則圖G的3個度結(jié)合路點主子圖可重構(gòu)圖G；若n≥5，則圖G的4個度結(jié)合路點主子圖可重構(gòu)圖G。

此時，圈分支Cm中至少存在1個點與v'不相鄰，故在圖H中刪除1個異于v'的m+1-度或m+2-度點后得到的主子圖比已知的另一路點主子圖多1個2-度點。

斷言2：新點v'的另2個鄰點分別是主子圖G-uk的2個冠圖分支中的m+1-度點，假設(shè)斷言不成立，分以下兩種情形討論：

情形2.2 新點v'的另2個鄰點{ua,ub}分別落在主子圖G-uk的2個冠圖分支中，當(dāng)ua,ub均是m+2-度點時，則從圖H刪除異于v'的m+2-度點得到的主子圖的割邊數(shù)至少比已知的路點主子圖少1；當(dāng)ua,ub中其中1個是m+2-度點時，不妨假設(shè)是ua且在冠圖分支Pn1oCm中，此時，n1≥3且圖H存在1個m+3-度點，由已知的另一路點主子圖中無m+3-度點可知，欲得到已知的另一路點主子圖，則刪除的點與ua相鄰，則圖H與G至多有3個相同的路點主子圖；當(dāng)ua,ub至少有1個為3-度點時，則在圖H刪除異于v'的m+1-度或m+2-度點后得到的主子圖中連通分支數(shù)比已知的路點主子圖至少多1個或者不存在圈分支。故情形2.2不成立。

綜上分析，引理得證。

證明：當(dāng)n=1時，由定理1可知，drn(G)=1。當(dāng)n=2且m=3時，圖G的度結(jié)合主子圖集里存在3個相同的度結(jié)合圈點主子圖，由引理2.2可知，drn(G)=3。除此之外，圖G的度結(jié)合主子圖集里存在1個度結(jié)合路點主子圖和1個度結(jié)合圈點主子圖，由引理2.1可知，drn(G)=2。

當(dāng)n∈{2,3,4}時，由圖2與圖G有2個公共的度結(jié)合主子圖(G-u1,m+1)可知，adrn(G)≥3。當(dāng)n≥5時，由圖3與圖G有3個公共的度結(jié)合主子圖(2個(G-u1,m+1)和1個(G-uk(≠1),m+2))可知，adrn(G)≥4。

圖2 與圖G有2個公共的度結(jié)合主子圖

圖3 與圖G有3個公共的度結(jié)合主子圖

下面證明確定值的上界。

當(dāng)n∈{3,4}時，由引理2.1，2.2，2.3可知，圖G的任意3個度結(jié)合主子圖可重構(gòu)圖G，故adrn(G)≤3。

當(dāng)n≥5時，由引理2.1，2.2，2.3可知，圖G的任意4個度結(jié)合主子圖可重構(gòu)圖G，故adrn(G)≤4。

當(dāng)n=2時，要證圖G的任意3個度結(jié)合主子圖可重構(gòu)圖G，由引理2.1和2.2可知，只需證當(dāng)m=3時，圖G的1個(G-u1,4)和2個(G-v1,3)或者2個(G-u1,4)和1個(G-v1,3)可以重構(gòu)圖G。令圖H表示在路點主子圖G-u1中添加1個4-度點v'后得到的不同構(gòu)于圖G的重構(gòu)圖，由已知的圈點主子圖G-v1可知重構(gòu)圖H是連通圖，故新點v'的鄰點落在G-u1的所有分支中，當(dāng)v'的1個鄰點落在圈分支C3中，則圖H至多只有1個(G-u1,4)和1個(G-v1,3)；當(dāng)v'的2個鄰點落在圈分支C3中，則圖H至多只有1個(G-u1,4)，所以adrn(G)≤3。