几类特殊的Gallai图

发布时间：2020-04-16 12:51

【摘要】：设G是一个E(G)非空的图.图G的Gallai图Gal(G)是把G的边集作为它的点集,若G中的两条边e和f是相邻的但不在同一个三角形中,则Gal(G)中的两个不同顶点e和f是相邻的.显然,图G的Gallai图Gal(G)是线图L(G)的一个生成子图.本文我们首先刻画了Gallai图分别是圈和完全k-部图的原图.我们证明了两个结论:一个图G的Gallai图Gal(G)是一个圈当且仅当G是F1,F3,F5或者Ck(k≥ 4)(见图2);图G是一个简单图,图G的Gallai图Gal(G)是一个完全k-部图当且仅当G是k-star(k ≥ 2),P4或者C4.著名图论学者Chartrand和Kronk证明了只有完全图、完全二部图和圈可以使得其任意线性森林可以扩充成哈密顿路.本文的剩余部分我们研究了任意线性森林可以扩充成哈密顿圈的图的刻画,在不应用Chartrand和Kronk结论的情况下本文给出一个直接的结构刻画.
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】