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

石黃萍,袁鄧彬,張芬

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

1 相關(guān)知識

在20世紀中葉，圖的重構(gòu)猜想是由Ulam在文獻[1]和Kelly在文獻[2]中提出并研究，它是指每個至少有3個頂點的圖都能被它的主子圖集所唯一確定，主子圖集是指所有主子圖組成的集合，而在圖G中刪除一個頂點v后得到的子圖稱為主子圖，記為G-v。之后，許多學者對圖的重構(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)問題，很多學者已經(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ù)。……