类星图的2种度结合重构数*1

周婷婷， 马美杰

（浙江师范大学数理与信息工程学院，浙江金华　321004）

类星图的2种度结合重构数*1

周婷婷， 马美杰

（浙江师范大学数理与信息工程学院，浙江金华321004）

通过分析类星图的一个度结合主子图可能重构的图的结构，确定了它的2种度结合重构数.研究类星图的重构数推广了星图的相关结论，丰富了结构图论的内容.

类星图；重构；主子图；度结合重构数

0　引言

重构猜想［1］的内容是：若图G和H分别是包含n（≥3）个顶点ui和vi的图（i=1，2，…，n），且对于所有的i都有G-ui同构于H-vi，则G和H同构.主子图是指在图G中删除一个点v后得到的子图，记为G-v.主子图族是指由图G的所有主子图构成的多重集合.若图G可以由它的主子图族唯一确定，则称图G是可重构的.重构猜想可以叙述为：至少有3个顶点的简单图都是可重构的.

1985年，Harary等［2］介绍了重构数的概念.重构数是指能重构图G所需的主子图的最少数目，记为rn（G）.此后，Myrvold［3］和Bollobás［4］证明了几乎所有图的重构数为3.用d（v）表示图G中顶点v的度. 1981年，Ramachandran［5］在有向图的研究中给出了度结合主子图的概念，并定义了度结合重构数.度结合主子图由主子图G-v和删除点的点度d（v）组成，记为（G-v，d（v））.度结合重构数是指能重构图G所需的度结合主子图的最少个数，记为drn（G）.一致度结合重构数是指任意k个度结合主子图都能重构图G的最小整数k，记为adrn（G）.2010年，Barrus等［6］证明了几乎所有图都有drn（G）≤2；2013年，Monikandan等［7］确定了当图G为路、圈、轮图、星图、完全图或完全二部图时drn（G）和adrn（G）的值；2015年，石黄萍等［8］确定了冠图P2·Cm的2种度结合边重构数；Monikandan等［9］确定了类星图的度结合边重构数和一致度结合边重构数的值.通过分析类星图的一个度结合主子图重构的图的结构，本文确定并证明了类星图的度结合重构数的值是1或2.一般情况下，一致度结合重构数的值为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）剖分与叶子关联的一条2-边1次后得到的图，记作T'（m，n）.

图K（m，n）的度结合主子图族中的元素如下：1个（mP1+nP2，m+n），称该类主子图为中心度结合主子图；m个（K（m-1，n），1），称该类主子图为第一类叶子度结合主子图；n个（K（m+1，n-1），1），称该类主子图为第二类叶子度结合主子图；n个（P1+K（m，n-1），2），称该类主子图为二点度结合主子图.第一类叶子度结合主子图和第二类叶子度结合主子图统称为叶子度结合主子图.叶子主子图是一棵树.对于K（1，1），第一类叶子度结合主子图与第二类叶子度结合主子图相同，中心度结合主子图与二点度结合主子图相同.

1　主要结果

令S表示由图K（m，n）的度结合主子图构成的一个集合.

引理1若S含有一个叶子度结合主子图，则重构图是一棵树；又若S还含有一个中心度结合主子图，则S可重构图K（m，n）.特别地，若n=0，则中心度结合主子图可重构图K（m，0）.

证明设S含有一个叶子度结合主子图.因为叶子主子图是一棵树，且对树的任意一个顶点悬挂一个1-点后仍为一棵树，所以重构图是一颗树.设S还含有中心度结合主子图，由中心主子图mP1+nP2重构图G.由于重构图G是一棵树，新添加的（m+n）-点x的邻点必定是m个孤立点和n个P2中的一个顶点，所以G≌K（m，n）.当n=0时，由（mP1，m）重构图G，新添加的m-点x的邻点必定是m个孤立点，所以G≌K（m，0）.引理1证毕.

引理2若m=0，则中心度结合主子图和1个二点度结合主子图可重构图K（m，n）；若m≥1，n≥3，则中心度结合主子图和3个二点度结合主子图可重构图K（m，n）.

证明由中心度结合主子图（mP1+nP2，m+n）重构图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的度结合主子图族中有2个（P1+K（m，n-1），2）和1个（mP1+nP2，m+n）.所以，G与K（m，n）有min｛2，n｝+1个相同的度结合主子图.

2）G含有1个3-圈和1个P2分支.删除G中不在3-圈上的点得到的主子图含有圈，删除G中3-圈上除x外的点得到的主子图为P2+K（m+1，n-1）.因此，G与K（m，n）的度结合主子图族只有1个公共的（mP1+nP2，m+n）.

3）G含有3-圈的个数不小于2.删除G中除x外的任一个点得到的主子图仍有圈.因此，G与K（m，n）的度结合主子图族只有1个公共的（mP1+nP2，m+n）.

因为当m=0时情况1）不会发生，所以中心度结合主子图和1个二点度结合主子图可重构K（m，n）.若m≥1，n≥3，则由上述讨论知，当由（mP1+nP2，m+n）重构的图G与K（m，n）不同构时，G的度结合主子图族中至多有2个（P2+K（m+1，n-1），2）.因此，中心度结合主子图和3个二点度结合主子图可重构K（m，n）.引理2证毕.

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

推论1若|S|≥4且S中含有中心度结合主子图，则S可重构图K（m，n）.

引理3若m≥1，n≥1且m+n≥4，则2种不同的叶子度结合主子图可重构图K（m，n）；1个第一类叶子度结合主子图和2个二点度结合主子图可重构图K（m，n）；若（m，n）≠（2，2），则2个第一类叶子度结合主子图和1个二点度结合主子图可重构图K（m，n）；若m+n≥4，（m，n）≠（3，1）且m-1＞n，则n+2个第一类叶子度结合主子图可重构图K（m，n）.

证明由第一类叶子度结合主子图（K（m-1，n），1）重构图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）的度结合主子图族含有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）的度结合主子图族有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后得到的度结合主子图分别是（K（m-1，n），1）和（P1+K（m，n-1））.当m+n≥4时，K'（m-1，n）的其他度结合主子图都与K（m，n）的度结合主子图不同.因此，K'（m-1，n）与K（m，n）的度结合主子图族有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后得到的度结合主子图都是（K（m-1，n），1）.当m+n≥5或（m，n）=（1，3）时，T（m-1，n）的其他度结合主子图都与K（m，n）的度结合主子图不同.因此，T（m-1，n）与K（m，n）的度结合主子图族有min｛m，2｝个公共的（K（m-1，n），1）.当m+n=4时，K（3，1）与T（2，1）的度结合主子图族有3个公共的（K（2，1），1），K（2，2）与T（1，2）的度结合主子图族有2个公共的（K（1，2），1）和1个公共的（K1+K（2，1），2）.

综合以上3种情况，若m+n≥4且由（K（m-1，n），1）重构的图G与K（m，n）不同构，则G的度结合主子图族中不含（K（m+1，n-1），1），至多含有1个（P1+K（m，n-1），2）.因此，不同的叶子度结合主子图可重构图K（m，n）；1个第一类叶子度结合主子图和2个二点度结合主子图可重构图K（m，n）.若（m，n）≠（2，2），则2个第一类叶子度结合主子图和1个二点度结合主子图可重构图K（m，n）.若（m，n）≠（3，1）且m-1＞n，则G与K（m，n）的度结合主子图族至多有n+1个公共的第一类叶子度结合主子图.所以，n+2个第一类叶子度结合主子图可重构图K（m，n）.引理3证毕.

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

推论2若m+n≥4，（m，n）≠（2，2），|S|≥3且S含有第一类叶子度结合主子图和其他度结合主子图，则S可重构图K（m，n）.

引理4若m+n≥4，则1个第二类叶子度结合主子图和1个二点度结合主子图可重构图K（m，n）；若n＞m+2，则m+3个第二类叶子度结合主子图可重构图K（m，n）.

证明由第二类叶子度结合主子图（K（m+1，n-1），1）重构图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）的度结合主子图族含有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）的度结合主子图族有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后得到的度结合主子图都是（K（m+1，n-1），1）.当m+n≥4时，T（m+1，n-1）的其他度结合主子图都与K（m，n）的度结合主子图不同.因此，T（m+1，n-1）与K（m，n）的度结合主子图族有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后得到的度结合主子图是（K（m+1，n-1），1）.当m+n≥4时，K'（m+1，n-1）的其他度结合主子图都与K（m，n）的度结合主子图不同.因此，K'（m+1，n-1）与K（m，n）的度结合主子图族有1个公共的（K（m+1，n-1），1）.

综合以上3种情况，当m+n≥4且由（K（m+1，n-1），1）重构的图G与K（m，n）不同构时，G的度结合主子图族中不含（P1+K（m，n-1），2）.所以，1个第二类叶子度结合主子图和1个二点度结合主子图可重构图K（m，n）.当n＞m+2时，G与K（m，n）的度结合主子图族至多有m+2个公共的（K（m+1，n-1），1）.所以，m+3个第二类叶子度结合主子图可重构图K（m，n）.引理4证毕.

由引理2—引理4可得到下面2个推论：

推论3当m+n≥4时，1个第二类叶子度结合主子图和1个其他度结合主子图可重构图K（m，n）.

推论4若m+n≥4，|S|≥4且S中含有不同类型的度结合主子图，则S可重构图K（m，n）.

引理5当m+n≥4且n≥3时，3个二点度结合主子图可重构图K（m，n）.

证明由二点度结合主子图（P1+K（m，n-1），2）重构图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）的度结合主子图族有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后得到的度结合主子图是（P1+K（m，n-1），2）.当m+n≥4时，K"（m，n-1）的其他度结合主子图都与K（m，n）的度结合主子图不同.因此，K"（m，n-1）与K（m，n）的度结合主子图族有1个公共的（P1+K（m，n-1），2）.

③G≌T'（m，n-1）.即在主子图P1+K（m，n-1）中添加点x与2-点相邻.删除T'（m，n-1）中的点x后得到的度结合主子图是（P1+K（m，n-1），2）.当m+n≥5或（m，n）=（0，4）时，T'（m，n-1）的其他度结合主子图都与K（m，n）的度结合主子图不同.因此，T'（m，n-1）与K（m，n）的度结合主子图族有1个公共的（P1+K（m，n-1），2）.当m+n=4时，K（1，3）与T'（1，2）的度结合主子图族有2个公共的（P1+K（1，2），2）.

2）G有2个连通分支.即添加点x的2个邻点都在K（m，n-1）中.重构图含有圈.删除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）的度结合主子图族至多有 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）的度结合主子图族至多有2个公共的（P1+K（m，n-1），2）.

②添加点x与K（m，n-1）的某个2-点y相邻，不与中心点u相邻.重构图G中有圈C，y与u相邻且点度都不小于2.因为K（m，n）中至多有1个点的度大于1，所以要得到与K（m，n）相同的主子图，必须删去y或u在圈C上的2-邻点.圈C上至多有2个这样的点.因此，G与K（m，n）的度结合主子图族至多有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）的度结合主子图族有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）的度结合主子图族有2个公共的（P1+K（m，n-1），2）.当l=6时，删除圈C6上不同于x的2-点后得到的主子图不是K（m，n）的主子图，故G与K（m，n）的度结合主子图族有1个公共的（P1+K（m，n-1），2）.

定理1若m+n≥1，则

证明当n=0时，由引理1知，中心度结合主子图可重构图K（m，0）.当n≥1时，任一度结合主子图的重构图不唯一，故drn（K（m，n））≥2.由引理1知，中心度结合主子图和一个叶子度结合主子图可重构K（m，n）.定理1证毕.

定理2若m+n≥1，则

证明因为K（1，0）≌P2，K（2，0）≌P3，且它们的任一度结合主子图的重构图唯一，所以，当（m，n）∈｛（1，0），（2，0）｝时，adrn（K（m，n））=1.下面讨论其余情况.

下界：图K（m+2，n-1）与K（m，n）有min｛m+2，n｝个公共的度结合主子图（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个公共的度结合主子图（K（m-1，n），1）.所以，adrn（K（m，n））≥n+2.

K（0，2）和K（2，1）的度结合主子图族有2个公共的（K（1，1），1）和1个公共的（P1+K（2，0），2）；K（0，3）和P1+C6的度结合主子图族有3个公共的（P1+K（0，2），2）；K（1，2）和P6的度结合主子图族有1个公共的（K（0，2），1）和2个（P1+K（1，1），2）；K（3，1）与T（2，1）的度结合主子图族有3个公共的（K（2，1），1）；K（2，2）与T（1，2）的度结合主子图族有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）的度结合主子图族有2个公共的（K（0，1），1），所以，当（m，n）∈｛（3，0），（1，1）｝时，adrn（K（m，n））≥3.

上界：令S表示由K（m，n）的度结合主子图构成的一个集合.G表示可由S重构的图.当3≤n∈｛m，m+1｝，|S|=n+1，或（m，n）∈｛（2，2），（3，1）｝且|S|=4时，S含有不同的度结合主子图，由推论4知，S可重构图K（m，n）.当m+n≥4且|S|≥4时，由推论4知，只需考虑S中仅含有1种度结合主子图的情况.

1）n≥m+2且|S|=m+3.当m≥1时，|S|≥4.当n=m+2时，S中含有2种不同的度结合主子图.只考虑n＞m+2且S含有m+3个（K（m+1，n-1），1）或m+3个（P1+K（m，n-1），2）的情况.由引理4和引理5知，S可重构K（m，n）.当m=0，n≥4时，|S|=3.若S中含有不同的度结合主子图，则由引理1—引理4知，S可重构K（0，n）.若S中只含有一种度结合主子图，则S含有3个（K（1，n-1），1）或3个（P1+K（0，n-1），2）.由引理4和引理5知，S可重构K（0，n）.

2）n≤m-1且|S|=n+2.当n≥2时，|S|≥4.当n=m-1时，S中含有2种不同的度结合主子图.只考虑n＜m-1且S含有n+2个（K（m-1，n），1）的情况.由引理3知，n+2个（K（m-1，n），1）可重构K（m，n）.当m≥4且n=1时，|S|=3.则S中一定含有（K（m-1，1），1）或（K（m+1，0），1）.若S含有不同的度结合主子图，则由推论2和推论3知S可重构K（m，1）；若S只含有1种度结合主子图（K（m-1，1），1），则由引理3知，3个（K（m-1，1），1）可重构K（m，1）；若m≥4，n=0且|S|=2，则S中一定含有（K（m-1，0），1）.由（K（m-1，0），1）重构的异于K（m，n）的图为K（m-2，1），它们的度结合主子图族有1个公共的（K（0，1），1）.所以，S可重构K（m，0）.

3）其余小情况.

对图K（0，2）≌P5.令|S|=4，则S中一定含有（K（1，1），1）和（P1+K（0，1），2）.由（K（1，1），1）重构且异于K（0，2）的图为K（2，1），它们的度结合主子图族没有4个公共的度结合主子图.所以，S可重构K（0，2）.

对图K（0，3）.令|S|=4.若S中含有中心度结合主子图，则由推论1知S可重构K（m，n）.若S中不含有中心度结合主子图，则一定含有（K（1，2），1）.由（K（1，2），1）重构且异于K（0，3）的图为K（2，2）或K'（1，2），它们与K（0，3）的度结合主子图族没有4个公共的度结合主子图.所以，S可重构K（0，3）.

对图K（1，2）.令|S|=4.若S中含有中心度结合主子图，则由推论1知S可重构K（m，n）；若S中不含有中心度结合主子图，则一定含有（K（2，1），1）.由（K（2，1），1）重构且异于K（1，2）的图为K（3，1），T（2，1）或K'（2，1），它们与K（1，2）的度结合主子图族没有4个公共的度结合主子图.所以，S可重构K（2，1）.

对图K（2，1）.若|S|=4，则S中一定含有（K（1，1），1）.由（K（1，1），1）重构且异于K（2，1）的重构图为K（0，2），它们的度结合主子图族没有4个公共的度结合主子图.所以，S可重构K（2，1）.

对图K（3，0）.若|S|=3，则S中一定含有（K（2，0），1）.由（K（2，0），1）重构且异于K（3，0）的图为K（1，1），它们的度结合主子图族有2个公共的（K（2，0），1）.所以，S可重构K（3，0）.

对图K（1，1）.若|S|=3，则S中一定含有（K（2，0），1）和（P1+P2，2）.由引理1知，S可重构K（1，1）.定理2证毕.

因为星图K1，m≌K（m，0），所以可由定理2得文献［7］中的如下结论：

2　结语

本文研究了一类比较特殊的树图——类星图，通过分析它的度结合主子图可能重构的图的结构，确定了类星图的2种度结合重构数.该研究方法和结果对研究树图的相关参数有一定的借鉴意义.我们将进一步研究一些特殊树图（如：直径为4的树图）的2种度结合重构数.

［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种度结合边重构数［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