乘積圖中的圖因子、子式、點(diǎn)著色邊賦權(quán)問(wèn)題.pdf

1、自從圖乘積引入到圖論中，它就和圖論的許多其他深刻而有趣的問(wèn)題建立了聯(lián)系，這個(gè)結(jié)合不僅使得圖乘積成為一種對(duì)圖操作的重要手段，同時(shí)在解決像Hamilton分解和Hadwiger猜想等這樣著名的問(wèn)題時(shí)，也激發(fā)出顯著的進(jìn)展，所有這些都?xì)w功于—個(gè)事實(shí)，那就是乘積圖是由較小的圖構(gòu)造而來(lái)并且繼承它們的性質(zhì)．與此同時(shí)，有些由一些簡(jiǎn)單的圖經(jīng)過(guò)圖乘積這樣復(fù)雜的操作而構(gòu)成的乘積圖本身也成為了研究的焦點(diǎn)，比如，Hamming圖和d-維立方體．在這個(gè)過(guò)程中，乘積

2、圖漸漸演變成解決數(shù)學(xué)中理論和應(yīng)用方面問(wèn)題的成熟而有效的工具．
　　 本文將致力于在乘積圖中研究一些圖論中的經(jīng)典問(wèn)題的最新結(jié)果，其中我們研究的乘積圖主要包括卡式積（口），強(qiáng)乘積（），字典積(o)三種．我們主要關(guān)注的是下面三個(gè)方面的問(wèn)題，(1)乘積圖和圖因子；在這個(gè)方面，我們要分別探究乘積圖的可擴(kuò)性和因子臨界性；(2)乘積圖和子式理論；(3)乘積圖中的點(diǎn)染色邊賦權(quán)問(wèn)題，本文第一章，我們簡(jiǎn)要介紹了本文將要用到的基本定義和符號(hào)．之后，我

3、們會(huì)介紹一些相關(guān)的背景知識(shí)，包括本文主要討論的三種乘積圖，因子可擴(kuò)性，因子臨界性，子式和點(diǎn)染色邊賦權(quán)等概念．在1.2節(jié)，我們簡(jiǎn)要介紹問(wèn)題的相關(guān)背景還有那些曾經(jīng)啟發(fā)我們進(jìn)行這些研究的已有的結(jié)果．
　　 在第二章中，我們首先介紹一些匹配可擴(kuò)性的結(jié)果，正是這些結(jié)果促使我們?cè)诔朔e圖中探究類(lèi)似的問(wèn)題，我們的主要工作是確定字典積圖的可擴(kuò)性，確切的說(shuō)，兩個(gè)連通圖Gl和G2分別是m-可擴(kuò)和n-可擴(kuò)，那么它們的字典積圖G20 G1是(m+1)(n

4、+1)一可擴(kuò)的，事實(shí)上，它也是2(m+1)(n+1)一因子臨界的．
　　 第三章主要包括兩個(gè)問(wèn)題:一個(gè)是卡式積圖的因子臨界性，另一個(gè)是在強(qiáng)乘積圖中的類(lèi)似問(wèn)題，在強(qiáng)乘積中，我們?cè)噲D在每種情況下證明出更好的結(jié)果．如果兩個(gè)連通圖G1和G2分別是m-因子臨界和n-因子臨界。(1)它們的卡式積G1口G2是[m+n+1]2(mn是偶數(shù))一因子臨界或者m+n+l(mn是奇數(shù))-因子臨界；以下的結(jié)果是關(guān)于強(qiáng)乘積圖的，(2)如果m≥0，n=0，I

5、V(G1)1≥2m+2并且IV(G2)≥4，那么GlG2是(2m+2)-因子臨界的；(3)如果n=1，IvG1≥2m+3，并且m≥3或者I(G2)l≥5，那么G1G2是(2m+4-ε)．因子臨界，此處若m是偶數(shù)，則ε=0，否則ε=1；(4)如果m+2≤Iv(G1)≤2m+2，或n+2≤Iv(G2)l≤2n+2，那么Gl囟G2是mm因子臨界；(5)如果Iv(G,)I≥2m+3并且IV(G2)l≥2n+3，那么G1G2是（mn一min因子臨

6、界．
　　 在第四章中，我們主要考慮一些特殊的乘積圖的子式問(wèn)題，并且推廣了早先Kotlov[31]中的結(jié)論．我們證明了對(duì)任意簡(jiǎn)單連通圖G，若G是x(G)可染色的，那么GK2是圖G口Qr的子式，此處Q是—個(gè)r．維立方體，且r=X(G)．在本章結(jié)尾我們證明了一些強(qiáng)乘積圖滿足Hadwiger猜想．
　　 在第五章中，我們介紹了關(guān)于乘積圖與點(diǎn)著色邊賦權(quán)問(wèn)題的研究成果．點(diǎn)著色邊賦權(quán)問(wèn)題是和H-因子有著密切聯(lián)系的問(wèn)題，在這一章，我們