TY - GEN
T1 - Mixed connectivity of random graphs
AU - Gu, Ran
AU - Shi, Yongtang
AU - Fan, Neng
N1 - Funding Information:
Acknowledgement. R. Gu was partially supported by Natural Science Foundation of Jiangsu Province (No. BK20170860), National Natural Science Foundation of China, and Fundamental Research Funds for the Central Universities (No. 2016B14214). Y. Shi was partially supported by the Natural Science Foundation of Tianjin (No. 17JCQNJC00300) and the National Natural Science Foundation of China.
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 -