Combinatorics Seminar - Murong Xu

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

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

S M T W T F S
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 
10
 
11
 
12
 
13
 
14
 
15
 
16
 
17
 
18
 
19
 
20
 
21
 
22
 
23
 
24
 
25
 
26
 
27
 
28
 
29
 
30