線圖與若干典型圖類的交叉數(shù)研究.pdf

1、圖的交叉數(shù)是近代圖論中發(fā)展起來的一個重要概念，自從上個世紀(jì)五十年代初匈牙利數(shù)學(xué)家PaulTurán根據(jù)其在一個磚廠碰到的實際難題(Turán'sbrickfactoryproblem)，從而提出了交叉數(shù)的概念以來，圖的交叉數(shù)逐漸成為國際上一個非?；钴S的分支，使得很多圖論專家對這方面進(jìn)行了深入研究. 本文在第一章較為詳細(xì)地介紹了目前圖的交叉數(shù)研究的歷史與現(xiàn)狀，并簡要介紹一些與本文有關(guān)的交叉數(shù)的概念. 在第二章，著重研究圖及

2、其線圖的交叉數(shù)，給出了圖與其線圖的交叉數(shù)的有關(guān)性質(zhì)，并得到了一個圖與其線圖的交叉數(shù)為都為k的充分必要條件：設(shè)G為圖，cr(G)=k(k≥1)，其線圖為L(G).若cr(L(G))=k，則當(dāng)且僅當(dāng)下列條件成立：(1)△(G)≤4，且G中每個4-度點都是割點； (2)存在G的一個恰有k個交叉數(shù)的最優(yōu)畫法使得每條交叉的邊關(guān)聯(lián)G中的一個2度點. 該結(jié)果實質(zhì)性地推廣了StanislavJendrol’和MarianKle(s)(c

3、)的關(guān)于非平面圖和它的線圖的交叉數(shù)都是1結(jié)果. 然后在第三章、第四章以及第五章中，與已有文獻(xiàn)中使用的方法不同，用“局部點度修改法”，并結(jié)合組合方法和歸納原理，研究了完全3-部圖K1,4,n，K1,6,n，K1,7,n，K1,8,n和K2,4,n的交叉數(shù)問題，分別確定它們各自的交叉數(shù)：1.cr(K1,4,n)=n(n-1). 2.若Zarankiewicz猜想對m=7的情形成立，則有cr(K1,6,n)=9[n/2][n-

4、1/2]+6[n/2]. 3.若Zarankiewicz猜想對m=8的情形成立，則有cr(K1,7,n)=12[n/2][n-1/2]+9[n/2]. 4.若Zarankiewicz猜想對m≤9的情形成立，則有cr(K1,8,n)=16[n/2][n-1/2]+12[n/2]. 5.設(shè)G是完全3-部圖K2,4,n，則cr(G)=Z(6，n)+2n. 上述研究結(jié)果充實和發(fā)展了圖的交叉數(shù)的研究成果，推廣了Kl