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

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

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

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

4、+1)一可擴(kuò)的，事實(shí)上，它也是2(m+1)(n+1)一因子臨界的．
　　 第三章主要包括兩個問題:一個是卡式積圖的因子臨界性，另一個是在強(qiáng)乘積圖中的類似問題，在強(qiáng)乘積中，我們試圖在每種情況下證明出更好的結(jié)果．如果兩個連通圖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、界．
　　 在第四章中，我們主要考慮一些特殊的乘積圖的子式問題，并且推廣了早先Kotlov[31]中的結(jié)論．我們證明了對任意簡單連通圖G，若G是x(G)可染色的，那么GK2是圖G口Qr的子式，此處Q是—個r．維立方體，且r=X(G)．在本章結(jié)尾我們證明了一些強(qiáng)乘積圖滿足Hadwiger猜想．
　　 在第五章中，我們介紹了關(guān)于乘積圖與點(diǎn)著色邊賦權(quán)問題的研究成果．點(diǎn)著色邊賦權(quán)問題是和H-因子有著密切聯(lián)系的問題，在這一章，我們