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

周婷婷， 馬美杰

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

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

周婷婷， 馬美杰

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

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

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

0　引言

重構(gòu)猜想［1］的內(nèi)容是：若圖G和H分別是包含n（≥3）個(gè)頂點(diǎn)ui和vi的圖（i=1，2，…，n），且對于所有的i都有G-ui同構(gòu)于H-vi，則G和H同構(gòu).主子圖是指在圖G中刪除一個(gè)點(diǎn)v后得到的子圖，記為G-v.主子圖族是指由圖G的所有主子圖構(gòu)成的多重集合.若圖G可以由它的主子圖族唯一確定，則稱圖G是可重構(gòu)的.重構(gòu)猜想可以敘述為：至少有3個(gè)頂點(diǎn)的簡單圖都是可重構(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中頂點(diǎn)v的度. 1981年，Ramachandran［5］在有向圖的研究中給出了度結(jié)合主子圖的概念，并定義了度結(jié)合重構(gòu)數(shù).度結(jié)合主子圖由主子圖G-v和刪除點(diǎn)的點(diǎn)度d（v）組成，記為（G-v，d（v））.度結(jié)合重構(gòu)數(shù)是指能重構(gòu)圖G所需的度結(jié)合主子圖的最少個(gè)數(shù)，記為drn（G）.一致度結(jié)合重構(gòu)數(shù)是指任意k個(gè)度結(jié)合主子圖都能重構(gòu)圖G的最小整數(shù)k，記為adrn（G）.2010年，Barrus等［6］證明了幾乎所有圖都有drn（G）≤2；2013年，Monikandan等［7］確定了當(dāng)圖G為路、圈、輪圖、星圖、完全圖或完全二部圖時(shí)drn（G）和adrn（G）的值；2015年，石黃萍等［8］確定了冠圖P2·Cm的2種度結(jié)合邊重構(gòu)數(shù)；Monikandan等［9］確定了類星圖的度結(jié)合邊重構(gòu)數(shù)和一致度結(jié)合邊重構(gòu)數(shù)的值.通過分析類星圖的一個(gè)度結(jié)合主子圖重構(gòu)的圖的結(jié)構(gòu)，本文確定并證明了類星圖的度結(jié)合重構(gòu)數(shù)的值是1或2.一般情況下，一致度結(jié)合重構(gòu)數(shù)的值為n+1，n+2或m+3，在幾個(gè)小情況中為1，3或4.

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

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

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

1　主要結(jié)果

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

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

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

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

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

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

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

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

因?yàn)楫?dāng)m=0時(shí)情況1）不會(huì)發(fā)生，所以中心度結(jié)合主子圖和1個(gè)二點(diǎn)度結(jié)合主子圖可重構(gòu)K（m，n）.若m≥1，n≥3，則由上述討論知，當(dāng)由（mP1+nP2，m+n）重構(gòu)的圖G與K（m，n）不同構(gòu)時(shí)，G的度結(jié)合主子圖族中至多有2個(gè)（P2+K（m+1，n-1），2）.因此，中心度結(jié)合主子圖和3個(gè)二點(diǎn)度結(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個(gè)第一類葉子度結(jié)合主子圖和2個(gè)二點(diǎn)度結(jié)合主子圖可重構(gòu)圖K（m，n）；若（m，n）≠（2，2），則2個(gè)第一類葉子度結(jié)合主子圖和1個(gè)二點(diǎn)度結(jié)合主子圖可重構(gòu)圖K（m，n）；若m+n≥4，（m，n）≠（3，1）且m-1＞n，則n+2個(gè)第一類葉子度結(jié)合主子圖可重構(gòu)圖K（m，n）.

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

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

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

3）G≌T（m-1，n）.即在主子圖K（m-1，n）中添加點(diǎn)x與某個(gè)2-點(diǎn)z相鄰，且點(diǎn)z與葉子y相鄰.對圖T（m-1，n），刪除點(diǎn)x，y后得到的度結(jié)合主子圖都是（K（m-1，n），1）.當(dāng)m+n≥5或（m，n）=（1，3）時(shí)，T（m-1，n）的其他度結(jié)合主子圖都與K（m，n）的度結(jié)合主子圖不同.因此，T（m-1，n）與K（m，n）的度結(jié)合主子圖族有min｛m，2｝個(gè)公共的（K（m-1，n），1）.當(dāng)m+n=4時(shí)，K（3，1）與T（2，1）的度結(jié)合主子圖族有3個(gè)公共的（K（2，1），1），K（2，2）與T（1，2）的度結(jié)合主子圖族有2個(gè)公共的（K（1，2），1）和1個(gè)公共的（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個(gè)（P1+K（m，n-1），2）.因此，不同的葉子度結(jié)合主子圖可重構(gòu)圖K（m，n）；1個(gè)第一類葉子度結(jié)合主子圖和2個(gè)二點(diǎn)度結(jié)合主子圖可重構(gòu)圖K（m，n）.若（m，n）≠（2，2），則2個(gè)第一類葉子度結(jié)合主子圖和1個(gè)二點(diǎn)度結(jié)合主子圖可重構(gòu)圖K（m，n）.若（m，n）≠（3，1）且m-1＞n，則G與K（m，n）的度結(jié)合主子圖族至多有n+1個(gè)公共的第一類葉子度結(jié)合主子圖.所以，n+2個(gè)第一類葉子度結(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個(gè)第二類葉子度結(jié)合主子圖和1個(gè)二點(diǎn)度結(jié)合主子圖可重構(gòu)圖K（m，n）；若n＞m+2，則m+3個(gè)第二類葉子度結(jié)合主子圖可重構(gòu)圖K（m，n）.

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

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

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

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

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

由引理2—引理4可得到下面2個(gè)推論：

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

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

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

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

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

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

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

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

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

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

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

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

定理1若m+n≥1，則

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

定理2若m+n≥1，則

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

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

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

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

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

2）n≤m-1且|S|=n+2.當(dāng)n≥2時(shí)，|S|≥4.當(dāng)n=m-1時(shí)，S中含有2種不同的度結(jié)合主子圖.只考慮n＜m-1且S含有n+2個(gè)（K（m-1，n），1）的情況.由引理3知，n+2個(gè)（K（m-1，n），1）可重構(gòu)K（m，n）.當(dāng)m≥4且n=1時(shí)，|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個(gè)（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個(gè)公共的（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個(gè)公共的度結(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個(gè)公共的度結(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個(gè)公共的度結(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個(gè)公共的度結(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個(gè)公共的（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證畢.

因?yàn)樾菆DK1，m≌K（m，0），所以可由定理2得文獻(xiàn)［7］中的如下結(jié)論：

2　結(jié)語

本文研究了一類比較特殊的樹圖——類星圖，通過分析它的度結(jié)合主子圖可能重構(gòu)的圖的結(jié)構(gòu)，確定了類星圖的2種度結(jié)合重構(gòu)數(shù).該研究方法和結(jié)果對研究樹圖的相關(guān)參數(shù)有一定的借鑒意義.我們將進(jìn)一步研究一些特殊樹圖（如：直徑為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］.浙江師范大學(xué)學(xué)報(bào)：自然科學(xué)版，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.

（責(zé)任編輯陶立方）

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

國家自然科學(xué)基金資助項(xiàng)目（11101378）

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

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