Premium
On k ‐Maximal Strength Digraphs
Author(s) -
Anderson Janet,
Lai HongJian,
Lin Xiaoxia,
Xu Murong
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22008
Subject(s) - digraph , constructive , combinatorics , mathematics , simple (philosophy) , characterization (materials science) , arc (geometry) , integer (computer science) , discrete mathematics , computer science , geometry , physics , philosophy , process (computing) , epistemology , optics , programming language , operating system
Let k > 0 be an integer and let D be a simple digraph on n > k vertices. We prove that If| A ( D ) | > k ( 2 n − k − 1 ) +n − k2, 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.