On the lower bound of kk-maximal digraphs

Research paper by Xiaoxia Lin, Suohai Fan, Hong-Jian Lai, Murong Xu

Indexed on: 21 May '16Published on: 18 May '16Published in: Discrete Mathematics


For a digraph DD, let λ(D)λ(D) be the arc-strong-connectivity of DD. For an integer k>0k>0, a simple digraph DD with |V(D)|≥k+1|V(D)|≥k+1 is kk-maximal if every subdigraph HH of DD satisfies λ(H)≤kλ(H)≤k but for adding new arc to DD results in a subdigraph H′H′ with λ(H′)≥k+1λ(H′)≥k+1. We prove that if DD is a simple kk-maximal digraph on n>k+1≥2n>k+1≥2 vertices, then