TY - GEN
T1 - Mixed connectivity of random graphs
AU - Gu, Ran
AU - Shi, Yongtang
AU - Fan, Neng
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - For positive integers k and λ, a graph G is (k,λ) -connected if it satisfies the following two conditions: (1) |V(G)|≥k+1, and (2) for any subset S⊆V(G) and any subset L⊆ E(G) with λ|S|+|L| < kλ, G-(S∪L) is connected. For positive integers k and ℓ, a graph G with |V(G)| ≥ k+ℓ+1 is said to be (k,ℓ)-mixed-connected if for any subset S⊆V(G) and any subset L⊆ E(G) with |S|≤ k,|L|≤ℓ and |S| + |L|< k+ℓ, G-(S∪ L) is connected. In this paper, we investigate the (k, λ) -connectivity and (k,ℓ)-mixed-connectivity of random graphs, and generalize the results of Erdős and Rényi (1959), and Stepanov (1970). Furthermore, our argument can show that in the random graph process G~=(Gt)0N, N=(n2), the hitting times of minimum degree at least kλ and of Gt being (k, λ) -connected coincide with high probability, and also the hitting times of minimum degree at least k+ ℓ and of Gt being (k, ℓ)-mixed-connected coincide with high probability. These results are analogous to the work of Bollobás and Thomassen (1986) on classic connectivity.
AB - For positive integers k and λ, a graph G is (k,λ) -connected if it satisfies the following two conditions: (1) |V(G)|≥k+1, and (2) for any subset S⊆V(G) and any subset L⊆ E(G) with λ|S|+|L| < kλ, G-(S∪L) is connected. For positive integers k and ℓ, a graph G with |V(G)| ≥ k+ℓ+1 is said to be (k,ℓ)-mixed-connected if for any subset S⊆V(G) and any subset L⊆ E(G) with |S|≤ k,|L|≤ℓ and |S| + |L|< k+ℓ, G-(S∪ L) is connected. In this paper, we investigate the (k, λ) -connectivity and (k,ℓ)-mixed-connectivity of random graphs, and generalize the results of Erdős and Rényi (1959), and Stepanov (1970). Furthermore, our argument can show that in the random graph process G~=(Gt)0N, N=(n2), the hitting times of minimum degree at least kλ and of Gt being (k, λ) -connected coincide with high probability, and also the hitting times of minimum degree at least k+ ℓ and of Gt being (k, ℓ)-mixed-connected coincide with high probability. These results are analogous to the work of Bollobás and Thomassen (1986) on classic connectivity.
KW - Connectivity
KW - Edge-connectivity
KW - Hitting time
KW - Random graph
KW - Threshold function
UR - http://www.scopus.com/inward/record.url?scp=85038217087&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85038217087&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-71150-8_13
DO - 10.1007/978-3-319-71150-8_13
M3 - Conference contribution
AN - SCOPUS:85038217087
SN - 9783319711492
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 133
EP - 140
BT - Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings
A2 - Han, Meng
A2 - Du, Hongwei
A2 - Gao, Xiaofeng
PB - Springer-Verlag
T2 - 11th International Conference on Combinatorial Optimization and Applications, COCOA 2017
Y2 - 16 December 2017 through 18 December 2017
ER -