競賽圖的生成三角形和包含給定弧的路圈問題.pdf

1、本文分為三章.文章主要討論了正則競賽圖的有向生成三角形問題和多部競賽圖中包含給定弧的路和圈問題.
　　第一章是預備知識，我們介紹了一些本文中將要用到的圖論方面的基本概念.
　　第二章，我們研究了正則競賽圖中生成三角形的問題，主要結(jié)果如下:
　　(1)設T是頂點個數(shù)為5的正則競賽圖，那么對于T的任意頂點x都存在生成T的2個有向三角形Ti使得V(Ti)∩ V(Tj)=x，其中1≤i＜j≤2.
　　(2)設T是頂點個數(shù)

2、為7的正則競賽圖，那么對于T的任意頂點x都存在生成T的3個有向三角形Ti使得V(Ti)∩ V(Tj)=x，其中1≤i＜j≤3.
　　(3)設T是頂點個數(shù)為9的正則競賽圖，那么對于T的任意頂點x都存在生成T的4個有向三角形Ti使得V(Ti)∩ V（Tj）=x，其中1≤i＜j≤4.
　　第三章，我們研究了多部競賽圖中包含給定弧的路和圈問題，主要結(jié)果如下:
　　(1)設D是階為n的c-部競賽圖，x，y是D中不同的頂點.如果c

3、≥5且n＞105ig(D)+2790，那么D中存在長為l的（x，y）-路P對任意的42≤l≤n-1成立.
　　(2)設D是階為n的c-部競賽圖其中c≥5，P是D中長為l的路，如果n＞105ig(D)+106l+2684，那么D中存在包含路P的H-圈.
　　(3)設D是階為n的c-部競賽圖其中c≥5，A={e1，e2…ek}是任意的k-可擴路弧集.如果n＞105ig(D)+2366+424k，那么D中存在包含弧集A的Hamil