与无向图及有向图中距离有关的三个问题

论文摘要

本文主要研究了与无向图及有向图中距离有关的三个问题:（1） KmV（?）（m≥1,n≥1）的最小直径定向,（2） 有向图中不相交的拟核,（3） 离心有向图。 对于图G,设D为G的具有最小直径的定向图,定义f（G）=diamD。本文我们主要探索图Km∨（?）（m≥1,n≥1）的最小直径定向。一些特殊情况是已知的:当m=1且n≥1;m=2或m≥4且n=1;m=3且n=1时,f（Km∨（?））分别为∞,2,3。因此,我们只考虑当m≥2且n≥2的情况,得到如下结果:（1） 当m=2,3,n≥2和m=n=4时,f（Km∨（?））=3;（2） 当m≥5且m是奇效,2≤n≤（?）-m时,f（Km∨（?））=2;（3） 当m≥5且m是奇数,n≥（?）-[m/2]+1时,f（Km∨（?））=3;（4） 当m≥4且m被4整除,2≤n≤（?）-（m/2+1）时,f（Km∨（?））=2;（5） 当m≥6且m被4除余2,2≤n≤（?）-m/2时,f（Km∨（?））=2;（6） 当m≥4且m是偶数,n≥（?）-m/2+1时,f（Km∨（?））=3。 设X为有向图D的一个顶点集,如果X是一个独立集并且X之外的每一个点都能经一步或两步到达X,则X称为D的一个拟核。本文我们给出了有向图中有一对不相交的拟核的一个必要条件和若干充分条件。 点v的离心距e（v）是D中v到其它所有点的最大距离。若如dD（v,u）=e（v）,则点u是点v的离心点。有向图D的离心有向图ED（D）与D有相同的顶点集且它的弧集定义如下:点u到点v有一条弧当且仅当点v是点u的一个离心点。无向图G的离心有向图ED（G）可以类似地定义。本文研究了几个无向图类和有向图类的离心有向图。设T是一个无向树,我们确定了ED2（T）的结构,这是[12]中提出的一个公开问题。

论文目录

• Abstract
• 摘要
• Chapter 1 Introduction
• 1.1 Definitions and notations
• 1.2 Some known results
• 1.3 Main results
• Chapter 2 The proofs of main results
• 2.1 Results about minimum diameter orientations
• 2.2 Results about disjoint quasi-kernels in digraphs
• 2.3 Results about eccentric digraphs
• Chapter 3 Several problems
• References
• 致谢