Note on the generalized connectivity.

Abstract: Let

S

be a nonempty set of vertices of a connected graph

G

. A collection

T_{1}, ..., T_{e} l l

of trees in

G

is said to be internally disjoint trees connecting

S

if

E (T_{i}) c a p E (T_{j}) = e m p t y s e t

and

V (T_{i}) c a p V (T_{j}) = S

for any pair of distinct integers

i, j

, where

1 l e q i, j l e q r

. For an integer

k

with

2 l e q k l e q n

, the generalized

k

-connectivity

k a p p a_{k} (G)

of

G

is the greatest positive integer

r

such that

G

contains at least

r

internally disjoint trees connecting

S

for any set

S

of

k

vertices of

G

. Obviously,

k a p p a_{2} (G)

is the connectivity of

G

. In this paper, sharp upper and lower bounds of

k a p p a_{3} (G)

are given for a connected graph

G

of order

n

, that is,

1 l e q k a p p a_{3} (G) l e q n - 2

. Graphs of order

n

such that

k a p p a_{3} (G) = n - 2, n - 3

are characterized, respectively.

Recommendations

Cited in

(41)

This page was built for publication: Note on the generalized connectivity.