The generalized 3-connectivity of random graphs

Publication date 11 February 2015

Abstract: The generalized connectivity of a graph

G

was introduced by Chartrand et al. Let

S

be a nonempty set of vertices of

G

, and

k a p p a (S)

be defined as the largest number of internally disjoint trees

T_{1}, T_{2}, c d o t s, T_{k}

connecting

S

in

G

. Then for an integer

r

with

2 l e q r l e q n

, the {it generalized

r

-connectivity}

k a p p a_{r} (G)

of

G

is the minimum

k a p p a (S)

where

S

runs over all the

r

-subsets of the vertex set of

G

. Obviously,

k a p p a_{2} (G) = k a p p a (G)

, is the vertex connectivity of

G

, and hence the generalized connectivity is a natural generalization of the vertex connectivity. Similarly, let

l a m b d a (S)

denote the largest number

k

of pairwise edge-disjoint trees

T_{1}, T_{2}, l d o t s, T_{k}

connecting

S

in

G

. Then the {it generalized

r

-edge-connectivity}

l a m b d a_{r} (G)

of

G

is defined as the minimum

l a m b d a (S)

where

S

runs over all the

r

-subsets of the vertex set of

G

. Obviously,

l a m b d a_{2} (G) = l a m b d a (G)

. In this paper, we study the generalized 3-connectivity of random graphs and prove that for every fixed integer

k g e q 1

,

p=frac{{log n+(k+1)log log n -log log log n}}{n}

is a sharp threshold function for the property

k a p p a_{3} (G (n, p)) g e q k

, which could be seen as a counterpart of Bollob'{a}s and Thomason's result for vertex connectivity. Moreover, we obtain that

d e l t a (G (n, p)) - 1 = l a m b d a (G (n, p)) - 1 = k a p p a (G (n, p)) - 1 l e k a p p a_{3} (G (n, p)) l e l a m b d a_{3} (G (n, p)) l e k a p p a (G (n, p)) = l a m b d a (G (n, p)) = d e l t a (G (n, p))

almost surely holds, which could be seen as a counterpart of Ivchenko's result.

Recommendations

Cited in

(12)

This page was built for publication: The generalized 3-connectivity of random graphs