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

石黃萍,袁鄧彬,張芬

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

1 相關(guān)知識(shí)

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

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

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

2 主要結(jié)果

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

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

斷言：新點(diǎn)v'與路點(diǎn)主子圖G-uk中的圈分支Cm中的每個(gè)點(diǎn)均相鄰。

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

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

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

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

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

斷言:新點(diǎn)v'至多有1個(gè)鄰點(diǎn)落在圈主子圖G-vi的路Pn上。

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

若新點(diǎn)v'有1個(gè)鄰點(diǎn)與G-vi的路Pn上的uk相鄰，其他的2個(gè)鄰點(diǎn){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-度點(diǎn)和3-度點(diǎn)，此時(shí)ui和uk是同一點(diǎn)，則圖H與G至多有2個(gè)相同的(G-vi,3)；當(dāng)va，vb均為G-vi中有公共鄰點(diǎn)的3-度點(diǎn)時(shí)，則圖H與G有2個(gè)相同的(G-vi,3)；當(dāng)va，vb均為G-vi中無(wú)公共鄰點(diǎn)的3-度點(diǎn)時(shí)，則圖H中增加2個(gè)4-度點(diǎn)，從中刪除異于v'的3-度點(diǎn)比已知的圈主子圖至少增加1個(gè)4-度點(diǎn)，故情形1不成立。

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

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

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

由以上分析，引理得證。

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

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

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

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

綜上分析，引理得證。

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

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

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

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

下面證明確定值的上界。

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

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

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