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 -