| 【论文摘要】 | 图论是一门年青但又快速成熟的学科,与其它学科如随机理论、群论、矩阵代数等结合发展了许多分支。然而在基础图论中仍然存在许多难题有待解决。本文就此研究了三个方面的内容:
第一部分考虑了L.Pyber[1]提出的问题:任意图可被至多三个奇子图所覆盖。我们证明了围长大于4的任意图均可被至多三个奇子图所覆盖。
第二部分考虑了与距离相关的问题。若顶点u,v在无向图G中是连通的,则定义G中最短的(u,v)?路的长为G中u,v之间的距离,记为dG(u,v) ; 若u,v在G中不连通,则定义dG(u,v)为无穷。称e(v) = Max {dG(v,u) ,?u∈V (G)}为顶点v的离心率(eccentricity)。若dG(u,v) = e(v) ,则称顶点u是v的一个离心点(eccentricvertex)。定义G的离心图(eccentric digraph)如下:顶点集为V (G) ,弧集满足:有一条弧从v到u当且仅当顶点u是v的一个离心点,记为ED(G)。给定一个正整数k≥2 ,EDk(G) = ED(EDk?1(G))其中ED0(G) = G。若存在最小整数p > 0和q≥0使得EDq(G) = EDp+... |
