Ohio State is in the process of revising websites and program materials to accurately reflect compliance with the law. While this work occurs, language referencing protected class status or other activities prohibited by Ohio Senate Bill 1 may still appear in some places. However, all programs and activities are being administered in compliance with federal and state law.

Combinatorics Seminar - Murong Xu

Murong Xu
February 14, 2019
10:00 am - 11:00 am
Math Tower 154

Title: On the sizes of $k$-maximal digraphs

SpeakerMurong 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$.

Events Filters: