有向图和二部有向图的局部边连通性

笔者首先利用顶点的度和给出了有向图是超级局部边连通的一个最好可能的充分条件,然后提出了二部有向图为极大局部边连通和超级局部边连通的度序列条件.这些结果在网络可靠性分析中有一定应用.

极大局部边连通和超级局部边连通二部有向图的邻域条件

本文主要证明了对于n阶二部有向图D,当最小度δ≥3,对任意同部顶点x,y,有min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}≥n+3/4时,D为极大局部边连通的;当最小度δ≥4,对任意同部顶点x,y,有min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}>n/4+1时,D为超级局部边连通的。我们证明了条件的最好可能性及结果与原有结果的独立性。

极大局部边连通和超级局部边连通有向图的度条件

证明了超级局部边连通有向图的最小度条件:如果n≤2δ,则排除一类图后,图为超级局部边连通的。此外还给出了极大局部边连通和超级局部边连通有向图的一些度序列条件。