关于二部图的两个结果

论文摘要

本文分为两章,第一章研究了连通无向图G的顶点扩张图（见定义1.13）的最小直径定向问题。图的最小直径定向问题的研究来自对单行街和流言问题的研究,目前这两个问题仍为研究的热点。单行街问题可以追溯到Robbins的经典论文[3],文[3]给出著名的单行街定理:一个连通的无向图G有强连通定向当且仅当G无桥。对一个无桥的连通无向图G,设Ω（G）表示G的强连通定向集合,对每一个D∈Ω（G）,我们用d（D）（相应d（G））表示D（相应G）的直径。定义（?）（G）=min{d（D）|D∈Ω（G）}。G（s1,s2,…,sn）（此记号来自[1]）为连通无向图G的顶点扩张图（n≥3,si≥2,i=1,2,…,n）,Koh和Tay在他们的论文[1]中得到不等式: d（G）≤（?）（G（s1,s2,…,sn））≤d（G）+2因而所有形如G（s1,s2,…,sn）的图被分为三类, φi={G（s1,s<sub>2,…,sn）|（?）（G（s1,s2,…,sn））=d（G）+i},i=0,1,2并且他们还提出一个猜想:如果G是直径至少为3的无向图,那么G的顶点扩张图不属于第三类图φ2,即G（s1,s2,…,sn）（?）φ2,（si≥2,i=1,2,…,n）,举出反例和给出证明都很困难,本文验证了对于一类特殊二部图—树,它的顶点扩张图是成立的,即当G是树时猜想是成立的。同时它也是文[1]中的一个结果的推广。 第二章中从图的不减度序列角度给出了一类度极大的非哈密尔顿简单平衡二部图,并且证明了:任何非哈密尔顿的简单平衡二部图,它的不减度序列一定弱于此类图中的某个图bm,n的度序列。本文给出了这类图bm,n的结构。

论文目录

• 第一章 一个猜想树的顶点扩张图中的印证
• §1.1 引言
• §1.2 预备知识
• §1.3 主要结果与证明
• 第二章 一个度极大的非哈密尔顿简单平衡二部图
• §2.1 引言
• §2.2 主要结果与证明
• 结论
• 参考文献
• 致谢
• 附录
• 承诺书