與無向圖及有向圖中距離有關(guān)的三個問題.pdf

1、本文主要研究了與無向圖及有向圖中距離有關(guān)的三個問題：(1)Km∨Kn(m≥1，n≥1)的最小直徑定向，(2)有向圖中不相交的擬核，(3)離心有向圖. 對于圖G，設(shè)D為G的具有最小直徑的定向圖，定義f(G)=diamD.本文我們主要探索圖Km∨Kn(m≥1，n≥1)的最小直徑定向.一些特殊情況是已知的：當(dāng)m=1且n≥1；m=2或m≥4且n=1；m=3且n=1時，f(Km∨Kn)分別為∞，2，3. 因此，我們只考慮當(dāng)m≥2且

2、n≥2的情況，得到如下結(jié)果：(1)當(dāng)m=2，3，n≥2和m=n=4時，f(Km∨Kn)=3；(2)當(dāng)m≥5且m是奇數(shù)，2≤n≤(m「m-2」)-m時，f(Km∨Kn)=2；(3)當(dāng)m≥5且m是奇數(shù)，n≥(m「m-2」)-「m-2」+1時，f(Km∨Kn)=3；(4)當(dāng)m≥4且m被4整除，2≤n≤(mm-2)-(m-2+1)時，f(Km∨Kn)=2；(5)當(dāng)m≥6且m被4除余2，2≤n≤(mm-2)-m-2時，f(Km∨Kn)=2；(6)

3、當(dāng)m≥4且m是偶數(shù)，n≥(mm-2)-m-2+1時，f(Km∨Kn)=3. 設(shè)X為有向圖D的一個璜點集，如果X是一個獨立集并且X之外的每一個點都能經(jīng)一步或兩步到達X，則X稱為D的一個擬核.本文我們給出了有向圖中有一對不相交的擬核的一個必要條件和若干充分條件. 點v的離心距e(v)是D中v到其它所有點的最大距離.若dD(v，u)=e(v)，則點u是點v的離心點.有向圖D的離心有向圖ED(D)與D有相同的頂點集且它的弧集定義