The minimal size of a graph with generalized connectivity _3=2

Publication date: 1 December 2011

Abstract: Let

G

be a nontrivial connected graph of order

n

and

k

an integer with

2 l e q k l e q n

. For a set

S

of

k

vertices of

G

, let

k a p p a (S)

denote the maximum number

e l l

of edge-disjoint trees

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

in

G

such that

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

for every pair

i, j

of distinct integers with

1 l e q i, j l e q e l l

. Chartrand et al. generalized the concept of connectivity as follows: The

k

-

c o n n e c t i v i t y

, denoted by

k a p p a_{k} (G)

, of

G

is defined by

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

min

k a p p a (S)

, where the minimum is taken over all

k

-subsets

S

of

V (G)

. Thus

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

, where

k a p p a (G)

is the connectivity of

G

. This paper mainly focuses on the minimal number of edges of a graph

G

with

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

. For a graph

G

of order

v (G)

and size

e (G)

with

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

, we obtain that

e (G) g e q 6 / 5 v (G)

, and the lower bound is sharp by showing a class of examples attaining the lower bound.

Recommendations

Cited In (18)

This page was built for publication: The minimal size of a graph with generalized connectivity \(\kappa_3=2\)