圖中匹配的可擴性研究--刻劃與閾.pdf

1、本文的主要研究是關于圖可擴性的一些進展,包括刻劃dicyclic群上Cayley圖的可擴性,確定1-可擴二部圖和bicritical圖的閾,以及確定k-factor-critical圖和k-可擴二部圖的閾。第一章首先介紹了關于匹配擴張的背景,并且給出了一些文中用到的定義和記號。同時,我們羅列出一些在主要結果的證明中用到的經(jīng)典定理。第二章給出了dicyclic群Q2n上的Cayley圖X(Q2n；S)的一個基本結構,并且由此證明了每個連通

2、的Cayley圖X(Q2n；S)是2-可擴的。我們進一步研究了X(Q2n；S)的3-可擴性。對于正則度數(shù)至多為5的情況,我們完全刻劃了其3-可擴性,并且猜想正則度數(shù)大于5的dicyclic群上Cayley圖都是3-可擴的。第三章研究了隨機圖的1-可擴性質(zhì)和bicritical性質(zhì)。注意對二部圖1-可擴性質(zhì)和bicritical性質(zhì)都是增性質(zhì),我們確定了它們的閾值。在一般隨機圖中1-可擴性質(zhì)不是單調(diào)的,然而我們給出了一個類似的閾函數(shù),當邊