TY - JOUR

T1 - Mixed connectivity properties of random graphs and some special graphs

AU - Gu, Ran

AU - Shi, Yongtang

AU - Fan, Neng

N1 - Funding Information:
R. Gu was partially supported by Natural Science Foundation of Jiangsu Province (No. BK20170860), National Natural Science Foundation of China (No. 11701143), and Fundamental Research Funds for the Central Universities (No. 2016B14214). Y. Shi was partially supported by National Natural Science Foundation of China (No. 11771221 and 11811540390), Natural Science Foundation of Tianjin (No. 17JCQNJC00300) and the China-Slovenia bilateral project “Some topics in modern graph theory” (No. 12-6).
Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2021/10

Y1 - 2021/10

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 (Publ Math Debrecen 6:290–297, 1959) and Stepanov (Theory Probab Appl 15:55–67, 1970). Furthermore, our argument 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 (Ann Discrete Math 28:35–38, 1986a; Combinatorica 7:35–38, 1986b) on classic connectivity. Additionally, we obtain the (k, λ) -connectivity and (k, ℓ) -mixed-connectivity of the complete graphs and complete bipartite graphs, and characterize the minimally (k, ℓ) -mixed-connected graphs.

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 (Publ Math Debrecen 6:290–297, 1959) and Stepanov (Theory Probab Appl 15:55–67, 1970). Furthermore, our argument 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 (Ann Discrete Math 28:35–38, 1986a; Combinatorica 7:35–38, 1986b) on classic connectivity. Additionally, we obtain the (k, λ) -connectivity and (k, ℓ) -mixed-connectivity of the complete graphs and complete bipartite graphs, and characterize the minimally (k, ℓ) -mixed-connected graphs.

KW - Connectivity

KW - Edge-connectivity

KW - Hitting time

KW - Mixed connectivity

KW - Random graph

KW - Threshold function

UR - http://www.scopus.com/inward/record.url?scp=85065969722&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065969722&partnerID=8YFLogxK

U2 - 10.1007/s10878-019-00415-z

DO - 10.1007/s10878-019-00415-z

M3 - Article

AN - SCOPUS:85065969722

SN - 1382-6905

VL - 42

SP - 427

EP - 441

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -