Title: On the sizes of $k$-maximal digraphs
Speaker: Murong Xu (Ohio State University)
Abstact: A digraph $D$ is strong if for any pair of vertices $u,v \in V(D)$, $D$ always contains a $(u,v)$-dipath. The strong arc connectivity of a digraph $D$, denoted by $\lambda(D)$, is the minmum number of arcs whose removal results in a non-strong digraph. If we just count the number of arcs in a digraph, can we predict that $D$ contains a subdigraph with high strong arc connectivity? We define $\bar{\lambda}(D) =$ max$\{\lambda(H) : H \subseteq D \}$. Given an integer $k > 0$, a strict digraph $D$ is $k$-minimal if $\bar{\lambda}(D) \leq k$ but adding any arc which is not in $D$ will surely create a subdigraph with strong arc connectivity at least $k+1$. Mader [Math. Ann. 1971] and Lai [JGT 1990] studied the extermal size of undirected $k$-maximal graphs. In this project, we determine that if $D$ is a $k$-maximal digraph on $n>k$ vertices, then
$${{n}\choose{2}} + (n-1)k+ \lfloor \frac{n}{k+2}\rfloor \left( 1+2k - {{k+2}\choose{2}}\right) \leq |A(D)| \leq k(2n-k-1) + {{n-k}\choose{2}}.$$
Consequently, if $|A(D)| > k(2n-k-1) + {{n-k}\choose{2}}$, then $D$ must have a nontrivial subdigraph $H$ such that the strong arc connectivity of $H$ is at least $k+1$.
