周婷婷， 馬美杰

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

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

周婷婷， 馬美杰

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

通過分析類星圖的一個度結(jié)合主子圖可能重構(gòu)的圖的結(jié)構(gòu)，確定了它的2種度結(jié)合重構(gòu)數(shù).研究類星圖的重構(gòu)數(shù)推廣了星圖的相關結(jié)論，豐富了結(jié)構(gòu)圖論的內(nèi)容.

類星圖；重構(gòu)；主子圖；度結(jié)合重構(gòu)數(shù)

0　引言

重構(gòu)猜想［1］的內(nèi)容是：若圖G和H分別是包含n（≥3）個頂點ui和vi的圖（i=1，2，…，n），且對于所有的i都有G-ui同構(gòu)于H-vi，則G和H同構(gòu).主子圖是指在圖G中刪除一個點v后得到的子圖，記為G-v.主子圖族是指由圖G的所有主子圖構(gòu)成的多重集合.若圖G可以由它的主子圖族唯一確定，則稱圖G是可重構(gòu)的.重構(gòu)猜想可以敘述為：至少有3個頂點的簡單圖都是可重構(gòu)的.

1985年，Harary等［2］介紹了重構(gòu)數(shù)的概念.重構(gòu)數(shù)是指能重構(gòu)圖G所需的主子圖的最少數(shù)目，記為rn（G）.此后，Myrvold［3］和Bollobás［4］證明了幾乎所有圖的重構(gòu)數(shù)為3.用d（v）表示圖G中頂點v的度. 1981年，Ramachandran［5］在有向圖的研究中給出了度結(jié)合主子圖的概念，并定義了度結(jié)合重構(gòu)數(shù).度結(jié)合主子圖由主子圖G-v和刪除點的點度d（v）組成，記為（G-v，d（v））.度結(jié)合重構(gòu)數(shù)是指能重構(gòu)圖G所需的度結(jié)合主子圖的最少個數(shù)，記為drn（G）.一致度結(jié)合重構(gòu)數(shù)是指任意k個度結(jié)合主子圖都能重構(gòu)圖G的最小整數(shù)k，記為adrn（G）.2010年，Barrus等［6］證明了幾乎所有圖都有drn（G）≤2；2013年，Monikandan等［7］確定了當圖G為路、圈、輪圖、星圖、完全圖或完全二部圖時drn（G）和adrn（G）的值；2015年，石黃萍等［8］確定了冠圖P2·Cm的2種度結(jié)合邊重構(gòu)數(shù)；Monikandan等［9］確定了類星圖的度結(jié)合邊重構(gòu)數(shù)和一致度結(jié)合邊重構(gòu)數(shù)的值.通過分析類星圖的一個度結(jié)合主子圖重構(gòu)的圖的結(jié)構(gòu)，本文確定并證明了類星圖的度結(jié)合重構(gòu)數(shù)的值是1或2.一般情況下，一致度結(jié)合重構(gòu)數(shù)的值為n+1，n+2或m+3，在幾個小情況中為1，3或4.

用Pn表示n（≥1）階路，Cl表示長為l的圈，長為3的圈記作3-圈.星圖K1，m是指m+1個頂點的樹，其中一個頂點（稱為中心）與其余m片葉子都相鄰.對圖G的邊e=uv，其邊度為d（e）=d（u）+ d（v）-2.圖G中點度為i的點稱作i-點，邊度為j的邊稱作j-邊.用G+H表示圖G和H的不相交并，用kG表示k個圖G的不相交并.

類星圖是由一個星圖K1，m+n通過剖分其中n條邊各1次后得到的圖，記作K（m，n），其中m+n≥1.稱這個星圖的中心為類星圖的中心.由星圖K1，m+n剖分其中n-1條邊各1次、1條邊2次后得到的圖，記作K'（m，n）.只有K'（0，1）=K（1，1）和K'（1，1）=K（0，2）是類星圖.由星圖K1，m+n剖分其中n-1條邊各1次、1條邊3次后得到的圖，記作K"（m，n）.只有K"（1，1）=K（0，2）是類星圖.在K（m，n）中與葉子相鄰的一個2-點上懸掛1片葉子后得到的圖，記作T（m，n）.只有T（0，1）=K（3，0）和T（1，1）= K（2，1）是類星圖.由T（m，n）剖分與葉子關聯(lián)的一條2-邊1次后得到的圖，記作T'（m，n）.

圖K（m，n）的度結(jié)合主子圖族中的元素如下：1個（mP1+nP2，m+n），稱該類主子圖為中心度結(jié)合主子圖；m個（K（m-1，n），1），稱該類主子圖為第一類葉子度結(jié)合主子圖；n個（K（m+1，n-1），1），稱該類主子圖為第二類葉子度結(jié)合主子圖；n個（P1+K（m，n-1），2），稱該類主子圖為二點度結(jié)合主子圖.第一類葉子度結(jié)合主子圖和第二類葉子度結(jié)合主子圖統(tǒng)稱為葉子度結(jié)合主子圖.葉子主子圖是一棵樹.對于K（1，1），第一類葉子度結(jié)合主子圖與第二類葉子度結(jié)合主子圖相同，中心度結(jié)合主子圖與二點度結(jié)合主子圖相同.

1　主要結(jié)果

令S表示由圖K（m，n）的度結(jié)合主子圖構(gòu)成的一個集合.

引理1若S含有一個葉子度結(jié)合主子圖，則重構(gòu)圖是一棵樹；又若S還含有一個中心度結(jié)合主子圖，則S可重構(gòu)圖K（m，n）.特別地，若n=0，則中心度結(jié)合主子圖可重構(gòu)圖K（m，0）.

證明設S含有一個葉子度結(jié)合主子圖.因為葉子主子圖是一棵樹，且對樹的任意一個頂點懸掛一個1-點后仍為一棵樹，所以重構(gòu)圖是一顆樹.設S還含有中心度結(jié)合主子圖，由中心主子圖mP1+nP2重構(gòu)圖G.由于重構(gòu)圖G是一棵樹，新添加的（m+n）-點x的鄰點必定是m個孤立點和n個P2中的一個頂點，所以G≌K（m，n）.當n=0時，由（mP1，m）重構(gòu)圖G，新添加的m-點x的鄰點必定是m個孤立點，所以G≌K（m，0）.引理1證畢.

引理2若m=0，則中心度結(jié)合主子圖和1個二點度結(jié)合主子圖可重構(gòu)圖K（m，n）；若m≥1，n≥3，則中心度結(jié)合主子圖和3個二點度結(jié)合主子圖可重構(gòu)圖K（m，n）.

證明由中心度結(jié)合主子圖（mP1+nP2，m+n）重構(gòu)圖G，即在（mP1+nP2）中添加一個（m+n）-點x.若GK（m，n），則G有下面3種情況：

1）G含有1個3-圈和1個P1分支.刪除G中不在3-圈上的點得到的主子圖含有圈，K（m，n）的主子圖都不含圈.刪除3-圈上任一個2-點得到主子圖P1+K（m，n-1）.因此，G的度結(jié)合主子圖族中有2個（P1+K（m，n-1），2）和1個（mP1+nP2，m+n）.所以，G與K（m，n）有min｛2，n｝+1個相同的度結(jié)合主子圖.

2）G含有1個3-圈和1個P2分支.刪除G中不在3-圈上的點得到的主子圖含有圈，刪除G中3-圈上除x外的點得到的主子圖為P2+K（m+1，n-1）.因此，G與K（m，n）的度結(jié)合主子圖族只有1個公共的（mP1+nP2，m+n）.

3）G含有3-圈的個數(shù)不小于2.刪除G中除x外的任一個點得到的主子圖仍有圈.因此，G與K（m，n）的度結(jié)合主子圖族只有1個公共的（mP1+nP2，m+n）.

因為當m=0時情況1）不會發(fā)生，所以中心度結(jié)合主子圖和1個二點度結(jié)合主子圖可重構(gòu)K（m，n）.若m≥1，n≥3，則由上述討論知，當由（mP1+nP2，m+n）重構(gòu)的圖G與K（m，n）不同構(gòu)時，G的度結(jié)合主子圖族中至多有2個（P2+K（m+1，n-1），2）.因此，中心度結(jié)合主子圖和3個二點度結(jié)合主子圖可重構(gòu)K（m，n）.引理2證畢.

由引理1和引理2得到下面推論：

推論1若|S|≥4且S中含有中心度結(jié)合主子圖，則S可重構(gòu)圖K（m，n）.

引理3若m≥1，n≥1且m+n≥4，則2種不同的葉子度結(jié)合主子圖可重構(gòu)圖K（m，n）；1個第一類葉子度結(jié)合主子圖和2個二點度結(jié)合主子圖可重構(gòu)圖K（m，n）；若（m，n）≠（2，2），則2個第一類葉子度結(jié)合主子圖和1個二點度結(jié)合主子圖可重構(gòu)圖K（m，n）；若m+n≥4，（m，n）≠（3，1）且m-1＞n，則n+2個第一類葉子度結(jié)合主子圖可重構(gòu)圖K（m，n）.

證明由第一類葉子度結(jié)合主子圖（K（m-1，n），1）重構(gòu)圖G，即在K（m-1，n）中添加一個1-點x.由引理1知，G是一棵樹.若m+n≥4，則葉子主子圖K（m-1，n）的中心點u的度大于2.若GK（m，n），則G有下面3種情況：

1）G≌K（m-2，n+1）.即在主子圖K（m-1，n）中添加點x與1-點y相鄰，且y與u相鄰.此時m≥2. K（m-2，n+1）的度結(jié)合主子圖族含有1個（（m-2）P1+（n+1）P2，m+n-1），n+1個（P1+K（m-2，n），2），n+1個（K（m-1，n），1）和m-2個（K（m-3，n+1），1）.當m+n≥4時，K（m-2，n+1）與K（m，n）的度結(jié)合主子圖族有min｛m，n+1｝個公共的（K（m-1，n），1）.

2）G≌K'（m-1，n）.即在主子圖K（m-1，n）中添加點x與1-點y相鄰，且點y與2-點z相鄰.對圖K'（m-1，n），刪除點x，y后得到的度結(jié)合主子圖分別是（K（m-1，n），1）和（P1+K（m，n-1））.當m+n≥4時，K'（m-1，n）的其他度結(jié)合主子圖都與K（m，n）的度結(jié)合主子圖不同.因此，K'（m-1，n）與K（m，n）的度結(jié)合主子圖族有1個公共的（K（m-1，n），1）和1個公共的（P1+K（m，n-1），2）.

3）G≌T（m-1，n）.即在主子圖K（m-1，n）中添加點x與某個2-點z相鄰，且點z與葉子y相鄰.對圖T（m-1，n），刪除點x，y后得到的度結(jié)合主子圖都是（K（m-1，n），1）.當m+n≥5或（m，n）=（1，3）時，T（m-1，n）的其他度結(jié)合主子圖都與K（m，n）的度結(jié)合主子圖不同.因此，T（m-1，n）與K（m，n）的度結(jié)合主子圖族有min｛m，2｝個公共的（K（m-1，n），1）.當m+n=4時，K（3，1）與T（2，1）的度結(jié)合主子圖族有3個公共的（K（2，1），1），K（2，2）與T（1，2）的度結(jié)合主子圖族有2個公共的（K（1，2），1）和1個公共的（K1+K（2，1），2）.

綜合以上3種情況，若m+n≥4且由（K（m-1，n），1）重構(gòu)的圖G與K（m，n）不同構(gòu)，則G的度結(jié)合主子圖族中不含（K（m+1，n-1），1），至多含有1個（P1+K（m，n-1），2）.因此，不同的葉子度結(jié)合主子圖可重構(gòu)圖K（m，n）；1個第一類葉子度結(jié)合主子圖和2個二點度結(jié)合主子圖可重構(gòu)圖K（m，n）.若（m，n）≠（2，2），則2個第一類葉子度結(jié)合主子圖和1個二點度結(jié)合主子圖可重構(gòu)圖K（m，n）.若（m，n）≠（3，1）且m-1＞n，則G與K（m，n）的度結(jié)合主子圖族至多有n+1個公共的第一類葉子度結(jié)合主子圖.所以，n+2個第一類葉子度結(jié)合主子圖可重構(gòu)圖K（m，n）.引理3證畢.

由引理1和引理3得到下面的推論：

推論2若m+n≥4，（m，n）≠（2，2），|S|≥3且S含有第一類葉子度結(jié)合主子圖和其他度結(jié)合主子圖，則S可重構(gòu)圖K（m，n）.

引理4若m+n≥4，則1個第二類葉子度結(jié)合主子圖和1個二點度結(jié)合主子圖可重構(gòu)圖K（m，n）；若n＞m+2，則m+3個第二類葉子度結(jié)合主子圖可重構(gòu)圖K（m，n）.

證明由第二類葉子度結(jié)合主子圖（K（m+1，n-1），1）重構(gòu)圖G.即在K（m+1，n-1）中添加一個1-點x.由引理1知，G是一棵樹.若m+n≥4，則葉子主子圖K（m+1，n-1）的中心點u的點度大于2. 若GK（m，n），則G有下面3種情況：

1）G≌K（m+2，n-1）.即在主子圖K（m+1，n-1）中添加點x與u點相鄰.K（m+2，n-1）的度結(jié)合主子圖族含有1個（（m+2）P1+（n-1）P2，m+n+1），n-1個（P1+K（m+2，n-2），2），n-1個（K（m+3，n-2），1）和m+2個（K（m+1，n-1），1）.當m+n≥4時，K（m+2，n-1）與K（m，n）的度結(jié)合主子圖族有min｛m+2，n｝個公共的（K（m+1，n-1），1）.

2）G≌T（m+1，n-1）.即在主子圖K（m+1，n-1）中添加點x與某個2-點z相鄰，且與z相鄰的葉子為y.刪除T（m+1，n-1）中的點x，y后得到的度結(jié)合主子圖都是（K（m+1，n-1），1）.當m+n≥4時，T（m+1，n-1）的其他度結(jié)合主子圖都與K（m，n）的度結(jié)合主子圖不同.因此，T（m+1，n-1）與K（m，n）的度結(jié)合主子圖族有2個公共的（K（m+1，n-1），1）.

3）G≌K'（m+1，n-1）.即在主子圖K（m+1，n-1）中添加點x與1-點y相鄰，且y與2-點相鄰.刪除K'（m+1，n-1）中的點x后得到的度結(jié)合主子圖是（K（m+1，n-1），1）.當m+n≥4時，K'（m+1，n-1）的其他度結(jié)合主子圖都與K（m，n）的度結(jié)合主子圖不同.因此，K'（m+1，n-1）與K（m，n）的度結(jié)合主子圖族有1個公共的（K（m+1，n-1），1）.

綜合以上3種情況，當m+n≥4且由（K（m+1，n-1），1）重構(gòu)的圖G與K（m，n）不同構(gòu)時，G的度結(jié)合主子圖族中不含（P1+K（m，n-1），2）.所以，1個第二類葉子度結(jié)合主子圖和1個二點度結(jié)合主子圖可重構(gòu)圖K（m，n）.當n＞m+2時，G與K（m，n）的度結(jié)合主子圖族至多有m+2個公共的（K（m+1，n-1），1）.所以，m+3個第二類葉子度結(jié)合主子圖可重構(gòu)圖K（m，n）.引理4證畢.

由引理2—引理4可得到下面2個推論：

推論3當m+n≥4時，1個第二類葉子度結(jié)合主子圖和1個其他度結(jié)合主子圖可重構(gòu)圖K（m，n）.

推論4若m+n≥4，|S|≥4且S中含有不同類型的度結(jié)合主子圖，則S可重構(gòu)圖K（m，n）.

引理5當m+n≥4且n≥3時，3個二點度結(jié)合主子圖可重構(gòu)圖K（m，n）.

證明由二點度結(jié)合主子圖（P1+K（m，n-1），2）重構(gòu)圖G.即在P1+K（m，n-1）中添加一個2-點x.若m+n≥4，則二點主子圖的連通分支K（m，n-1）的中心點u的點度大于2.若GK（m，n），則G有下面2種情況：

1）G是一顆樹.即添加點x的2個鄰點分別在P1和K（m，n-1）中.

①G≌K'（m-1，n）.由引理3的情況2）知，K'（m-1，n）與K（m，n）的度結(jié)合主子圖族有1個公共的（K（m-1，n），1）和1個公共的（P1+K（m，n-1），2）.

②G≌K"（m，n-1）.即在主子圖P1+K（m，n-1）中添加點x與1-點y相鄰，且y與2-點相鄰.刪除K"（m，n-1）中的點x后得到的度結(jié)合主子圖是（P1+K（m，n-1），2）.當m+n≥4時，K"（m，n-1）的其他度結(jié)合主子圖都與K（m，n）的度結(jié)合主子圖不同.因此，K"（m，n-1）與K（m，n）的度結(jié)合主子圖族有1個公共的（P1+K（m，n-1），2）.

③G≌T'（m，n-1）.即在主子圖P1+K（m，n-1）中添加點x與2-點相鄰.刪除T'（m，n-1）中的點x后得到的度結(jié)合主子圖是（P1+K（m，n-1），2）.當m+n≥5或（m，n）=（0，4）時，T'（m，n-1）的其他度結(jié)合主子圖都與K（m，n）的度結(jié)合主子圖不同.因此，T'（m，n-1）與K（m，n）的度結(jié)合主子圖族有1個公共的（P1+K（m，n-1），2）.當m+n=4時，K（1，3）與T'（1，2）的度結(jié)合主子圖族有2個公共的（P1+K（1，2），2）.

2）G有2個連通分支.即添加點x的2個鄰點都在K（m，n-1）中.重構(gòu)圖含有圈.刪除G中不在圈上的點后得到的主子圖含有圈，而K（m，n）的主子圖都不含圈.所以，下面只考慮刪除圈上點后的情況.

①添加點x與K（m，n-1）的中心點u相鄰.記x的另外一個鄰點為y，則點x，y，u在一個圈Cl上. 當l=3時，3-圈上至多有 2個 2-點.G與 K（m，n）的度結(jié)合主子圖族至多有 2個公共的（P1+K（m，n-1），2）.當l=4時，y是2-點z在K（m，n-1）中的葉鄰點，G-y不是K（m，n）的主子圖，G-z≌G-x.因此，G與K（m，n）的度結(jié)合主子圖族至多有2個公共的（P1+K（m，n-1），2）.

②添加點x與K（m，n-1）的某個2-點y相鄰，不與中心點u相鄰.重構(gòu)圖G中有圈C，y與u相鄰且點度都不小于2.因為K（m，n）中至多有1個點的度大于1，所以要得到與K（m，n）相同的主子圖，必須刪去y或u在圈C上的2-鄰點.圈C上至多有2個這樣的點.因此，G與K（m，n）的度結(jié)合主子圖族至多有2個公共的（P1+K（m，n-1），2）.

③添加點x，使得點x與K（m，n-1）的2個1-點y和點z相鄰，則點x，y，z在一個圈Cl上.當l=4時，G-z≌G-y，而G-y不是K（m，n）的主子圖，故G與K（m，n）的度結(jié)合主子圖族有1個公共的（P1+K（m，n-1），2）.當l=5時，不妨設y是2-點w的葉鄰點，G-z≌G-w，而G-z不是K（m，n）的主子圖，G-y≌G-x，故G與K（m，n）的度結(jié)合主子圖族有2個公共的（P1+K（m，n-1），2）.當l=6時，刪除圈C6上不同于x的2-點后得到的主子圖不是K（m，n）的主子圖，故G與K（m，n）的度結(jié)合主子圖族有1個公共的（P1+K（m，n-1），2）.

定理1若m+n≥1，則

證明當n=0時，由引理1知，中心度結(jié)合主子圖可重構(gòu)圖K（m，0）.當n≥1時，任一度結(jié)合主子圖的重構(gòu)圖不唯一，故drn（K（m，n））≥2.由引理1知，中心度結(jié)合主子圖和一個葉子度結(jié)合主子圖可重構(gòu)K（m，n）.定理1證畢.

定理2若m+n≥1，則

證明因為K（1，0）≌P2，K（2，0）≌P3，且它們的任一度結(jié)合主子圖的重構(gòu)圖唯一，所以，當（m，n）∈｛（1，0），（2，0）｝時，adrn（K（m，n））=1.下面討論其余情況.

下界：圖K（m+2，n-1）與K（m，n）有min｛m+2，n｝個公共的度結(jié)合主子圖（K（m+1，n-1），1）.當n≥m+2時，adrn（K（m，n））≥m+3；當n∈｛m，m+1｝時，adrn（K（m，n））≥n+1；當n≤m-1時，圖K（m-2，n+1）與K（m，n）有n+1個公共的度結(jié)合主子圖（K（m-1，n），1）.所以，adrn（K（m，n））≥n+2.

K（0，2）和K（2，1）的度結(jié)合主子圖族有2個公共的（K（1，1），1）和1個公共的（P1+K（2，0），2）；K（0，3）和P1+C6的度結(jié)合主子圖族有3個公共的（P1+K（0，2），2）；K（1，2）和P6的度結(jié)合主子圖族有1個公共的（K（0，2），1）和2個（P1+K（1，1），2）；K（3，1）與T（2，1）的度結(jié)合主子圖族有3個公共的（K（2，1），1）；K（2，2）與T（1，2）的度結(jié)合主子圖族有2個公共的（K（1，2），1）和1個公共的（P1+K（2，1），2）.所以，當（m，n）∈｛（0，2），（0，3），（1，2），（2，1），（2，2），（3，1）｝時，adrn（K（m，n））≥4.K（3，0）和K（1，1）的度結(jié)合主子圖族有2個公共的（K（0，1），1），所以，當（m，n）∈｛（3，0），（1，1）｝時，adrn（K（m，n））≥3.

上界：令S表示由K（m，n）的度結(jié)合主子圖構(gòu)成的一個集合.G表示可由S重構(gòu)的圖.當3≤n∈｛m，m+1｝，|S|=n+1，或（m，n）∈｛（2，2），（3，1）｝且|S|=4時，S含有不同的度結(jié)合主子圖，由推論4知，S可重構(gòu)圖K（m，n）.當m+n≥4且|S|≥4時，由推論4知，只需考慮S中僅含有1種度結(jié)合主子圖的情況.

1）n≥m+2且|S|=m+3.當m≥1時，|S|≥4.當n=m+2時，S中含有2種不同的度結(jié)合主子圖.只考慮n＞m+2且S含有m+3個（K（m+1，n-1），1）或m+3個（P1+K（m，n-1），2）的情況.由引理4和引理5知，S可重構(gòu)K（m，n）.當m=0，n≥4時，|S|=3.若S中含有不同的度結(jié)合主子圖，則由引理1—引理4知，S可重構(gòu)K（0，n）.若S中只含有一種度結(jié)合主子圖，則S含有3個（K（1，n-1），1）或3個（P1+K（0，n-1），2）.由引理4和引理5知，S可重構(gòu)K（0，n）.

2）n≤m-1且|S|=n+2.當n≥2時，|S|≥4.當n=m-1時，S中含有2種不同的度結(jié)合主子圖.只考慮n＜m-1且S含有n+2個（K（m-1，n），1）的情況.由引理3知，n+2個（K（m-1，n），1）可重構(gòu)K（m，n）.當m≥4且n=1時，|S|=3.則S中一定含有（K（m-1，1），1）或（K（m+1，0），1）.若S含有不同的度結(jié)合主子圖，則由推論2和推論3知S可重構(gòu)K（m，1）；若S只含有1種度結(jié)合主子圖（K（m-1，1），1），則由引理3知，3個（K（m-1，1），1）可重構(gòu)K（m，1）；若m≥4，n=0且|S|=2，則S中一定含有（K（m-1，0），1）.由（K（m-1，0），1）重構(gòu)的異于K（m，n）的圖為K（m-2，1），它們的度結(jié)合主子圖族有1個公共的（K（0，1），1）.所以，S可重構(gòu)K（m，0）.

3）其余小情況.

對圖K（0，2）≌P5.令|S|=4，則S中一定含有（K（1，1），1）和（P1+K（0，1），2）.由（K（1，1），1）重構(gòu)且異于K（0，2）的圖為K（2，1），它們的度結(jié)合主子圖族沒有4個公共的度結(jié)合主子圖.所以，S可重構(gòu)K（0，2）.

對圖K（0，3）.令|S|=4.若S中含有中心度結(jié)合主子圖，則由推論1知S可重構(gòu)K（m，n）.若S中不含有中心度結(jié)合主子圖，則一定含有（K（1，2），1）.由（K（1，2），1）重構(gòu)且異于K（0，3）的圖為K（2，2）或K'（1，2），它們與K（0，3）的度結(jié)合主子圖族沒有4個公共的度結(jié)合主子圖.所以，S可重構(gòu)K（0，3）.

對圖K（1，2）.令|S|=4.若S中含有中心度結(jié)合主子圖，則由推論1知S可重構(gòu)K（m，n）；若S中不含有中心度結(jié)合主子圖，則一定含有（K（2，1），1）.由（K（2，1），1）重構(gòu)且異于K（1，2）的圖為K（3，1），T（2，1）或K'（2，1），它們與K（1，2）的度結(jié)合主子圖族沒有4個公共的度結(jié)合主子圖.所以，S可重構(gòu)K（2，1）.

對圖K（2，1）.若|S|=4，則S中一定含有（K（1，1），1）.由（K（1，1），1）重構(gòu)且異于K（2，1）的重構(gòu)圖為K（0，2），它們的度結(jié)合主子圖族沒有4個公共的度結(jié)合主子圖.所以，S可重構(gòu)K（2，1）.

對圖K（3，0）.若|S|=3，則S中一定含有（K（2，0），1）.由（K（2，0），1）重構(gòu)且異于K（3，0）的圖為K（1，1），它們的度結(jié)合主子圖族有2個公共的（K（2，0），1）.所以，S可重構(gòu)K（3，0）.

對圖K（1，1）.若|S|=3，則S中一定含有（K（2，0），1）和（P1+P2，2）.由引理1知，S可重構(gòu)K（1，1）.定理2證畢.

因為星圖K1，m≌K（m，0），所以可由定理2得文獻［7］中的如下結(jié)論：

2　結(jié)語

本文研究了一類比較特殊的樹圖——類星圖，通過分析它的度結(jié)合主子圖可能重構(gòu)的圖的結(jié)構(gòu)，確定了類星圖的2種度結(jié)合重構(gòu)數(shù).該研究方法和結(jié)果對研究樹圖的相關參數(shù)有一定的借鑒意義.我們將進一步研究一些特殊樹圖（如：直徑為4的樹圖）的2種度結(jié)合重構(gòu)數(shù).

［1］Ulam SM.A collection ofmathematical problems［M］.New York-London：Interscience Publishers，1960：20.

［2］Harary F，Plantholt M.The graph reconstruction number［J］.JGraph Theory，1985，9（4）：451-454.

［3］Myrvold W.The ally-reconstruction number of a tree with five ormore vertices is three［J］.JGraph Theory，1990，14（2）：149-166.

［4］Bollobás B.Almost every graph has reconstruction number three［J］.JGraph Theory，1990，14（1）：1-4.

［5］Ramachandran S.On a new digraph reconstruction conjecture［J］.JCombin Theory Ser B，1981，31（2）：143-149.

［6］Barrus M D，West D B.Degree-associated reconstruction number of graphs［J］.Discrete Math，2010，310（20）：2600-2612.

［7］Monikandan S，Sundar R S，Jayasekaran C，et al.A note on the adversary degree associated reconstruction number of graphs［J］.JDiscrete Math，2013，2013：808105.

［8］石黃萍，馬美杰.冠圖P2·Cm的2種度結(jié)合邊重構(gòu)數(shù)［J］.浙江師范大學學報：自然科學版，2015，38（2）：176-178.

［9］Monikandan S，Anusha D P，Sundar R S.Degree associated edge reconstruction number of graphs［J］.JDiscrete Algorithms，2013，23：35-41.

（責任編輯陶立方）

Two degree-associated reconstruction numbers of star-like graphs

ZHOU Tingting， MA Meijie
（College of Mathematics，Physics and Information Engineering，Zhejiang Normal University，Jinhua 321004，China）

Two degree-associated reconstruction numbers of star-like graphs were determined by considering the possible reconstructions from a degree-associated card.The results generalized the related conclusions of star graphs.

star-like graph；reconstruction；card；degree-associated reconstruction number

O157.5

A

1001-5051（2016）02-0150-06

10.16218/j.issn.1001-5051.2016.02.005

*收文日期：2015-06-05；2015-06-29

國家自然科學基金資助項目（11101378）

周婷婷（1990-），女，廣東茂名人，碩士研究生.研究方向：運籌學與控制論；圖論.

馬美杰.E-mait：mameij@zjnu.cn