论文部分内容阅读
图的交叉数是近代图论中发展起来的一个重要概念,自从上个世纪五十年代初匈牙利数学家PaulTurán根据其在一个砖厂碰到的实际难题(Turánsbrickfactoryproblem),从而提出了交叉数的概念以来,图的交叉数逐渐成为国际上一个非常活跃的分支,使得很多图论专家对这方面进行了深入研究.
本文在第一章较为详细地介绍了目前图的交叉数研究的历史与现状,并简要介绍一些与本文有关的交叉数的概念.
在第二章,着重研究图及其线图的交叉数,给出了图与其线图的交叉数的有关性质,并得到了一个图与其线图的交叉数为都为k的充分必要条件:设G为图,cr(G)=k(k≥1),其线图为L(G).若cr(L(G))=k,则当且仅当下列条件成立:(1)△(G)≤4,且G中每个4-度点都是割点;
(2)存在G的一个恰有k个交叉数的最优画法使得每条交叉的边关联G中的一个2度点.
该结果实质性地推广了StanislavJendrol’和MarianKle(s)(c)的关于非平面图和它的线图的交叉数都是1结果.
然后在第三章、第四章以及第五章中,与已有文献中使用的方法不同,用“局部点度修改法”,并结合组合方法和归纳原理,研究了完全3-部图K1,4,n,K1,6,n,K1,7,n,K1,8,n和K2,4,n的交叉数问题,分别确定它们各自的交叉数:1.cr(K1,4,n)=n(n-1).
2.若Zarankiewicz猜想对m=7的情形成立,则有cr(K1,6,n)=9[n/2][n-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.设G是完全3-部图K2,4,n,则cr(G)=Z(6,n)+2n.
上述研究结果充实和发展了图的交叉数的研究成果,推广了Klesc关于星与5阶图的积图的交叉数结果,并提供了新的研究图的交叉数的方法.
本文最后简要介绍了作者今后研究的方向,同时指出了一些亟待解决的问题.