平面圖的z變換圖的連通性及對pm215;cn的強迫譜的應(yīng)用

1、分類號： O157 密級： 公開研 究 生 學(xué) 位 論 文論文題目(中文) 平面圖的 𝑍-變換圖的連通性及對 𝑃𝑚 × 𝐶𝑛 的強迫譜的應(yīng)用論文題目(外文) The Connectivity of 𝑍-transformation Graphof Plane Graphs with the Applications toForcin

2、g Spectrum of 𝑃𝑚 × 𝐶𝑛研 究 生 姓 名 王 景 峰學(xué) 科、 專業(yè) 數(shù)學(xué) 、應(yīng)用數(shù)學(xué)研 究 方 向 圖論及其應(yīng)用學(xué) 位 級 別 碩 士導(dǎo)師姓名、 職稱 張和平 教授論 文 工 作 起 止 年 月 2015 年 9 月 至 2017 年 3 月論文提交日期 2017 年 4 月論文答辯日期 2017 年 5 月學(xué)位授予日期校 址： 甘 肅 省 蘭

3、 州 市平面圖的 𝑍-變換圖的連通性及對 𝑃𝑚 × 𝐶𝑛 的強迫譜的應(yīng)用中文摘要設(shè) 𝐺 是一個平面圖. 𝐺 的 𝑍-變換圖 𝑍(𝐺) 的頂點集為 𝐺 的所有完美匹配的集合, 兩個頂點 𝑀1, 𝑀2 之間連邊當且僅當它們的對

4、稱差恰好是 𝐺 的某個內(nèi)面圈.本文首先證明了對于簡單平面圖 𝐺, 其 𝑍-變換圖是二部圖, 并且證明了 𝑍(𝐺) 連通的充要條件是, 對于 𝐺 的任意一個好圈 𝐶 , 𝐶 包括它的內(nèi)部一起構(gòu)成了一個平面基本二部圖. 由此推廣了平面二部圖的𝑍-變換圖的相應(yīng)的結(jié)論.對于圓柱圖, 利用上述充要條件我們

5、得到 𝑍(𝑃𝑚 × 𝐶𝑛)(𝑛 ?= 4) 去掉一度點是 2-連通的, 類似的結(jié)論在六角系統(tǒng)[16, 17]上已經(jīng)得到證明. 進一步, 我們也刻畫出了 𝑍(𝑃𝑚 × 𝐶𝑛) 的所有一度點. 具體講, 當 𝑛 為奇數(shù), 并且 |&

6、#119899; ? 𝑚| = 1 時,𝑍(𝑃𝑚 × 𝐶𝑛) 有 𝑛 個一度點, 且恰好有兩個同構(gòu)類, 其余情況沒有一度點; 當 𝑛 為偶數(shù)時, 有且僅有 2 個一度點, 它們所對應(yīng)的 𝐺 的完美匹配的所有的匹配邊都是水平的. 與此同時, 我們簡化了全局 𝑍-變換圖 &

7、#119885;𝑡(𝑃𝑚 × 𝐶2𝑛)(𝑛 ?= 2) 是 2-連通的證明.圖 𝐺 的所有完美匹配的強迫數(shù)所構(gòu)成的集合叫做 𝐺 的強迫譜. 最后, 利用平面圖的 𝑍-變換圖連通的充要條件證明了 𝑃2𝑚 × 𝐶2𝑛