On k-Maximal Strength Digraphs

被引：8

作者：

Anderson, Janet ^{[1
]}

Lai, Hong-Jian ^{[1
]}

Lin, Xiaoxia ^{[2
]}

Xu, Murong ^{[1
]}

机构：

[1] West Virginia Univ, Dept Math, Morgantown, WV 26506 USA

[2] Jimei Univ, Sch Sci, Xiamen 361021, Fujian, Peoples R China

来源：

JOURNAL OF GRAPH THEORY | 2017年 / 84卷 / 01期

关键词：

strong arc connectivity; subdigraph arc connectivity; extremal digraphs; GRAPHS;

D O I：

10.1002/jgt.22008

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let k>0 be an integer and let D be a simple digraph on n>k vertices. We prove that If vertical bar A(D)vertical bar > k(2n - k - 1) + (n - k 2), then D must have a nontrivial subdigraph H such that the strong arc connectivity of H is at least k+1. We also show that this bound is best possible and present a constructive characterization for the extremal graphs.

引用

页码：17 / 25

页数：9