Ohio State nav bar

Combinatorics Seminar - Murong Xu

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

Date Range
Add to Calendar 2019-02-14 10:00:00 2019-02-14 11:00:00 Combinatorics Seminar - Murong Xu 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$. Math Tower 154 Department of Mathematics math@osu.edu America/New_York public

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: