The generalized 3-connectivity of Cartesian product

Authors Hengzhe Li, Yuefang Sun, Xueliang Li

Publication date 25 March 2014

Full work available at URL https://arxiv.org/abs/1103.6095, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1850/0.html

zbMATH Keywords

connectivity internally disjoint trees generalized connectivity internally disjoint path

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Abstract: The generalized connectivity of a graph, which was introduced recently by Chartrand et al., is a generalization of the concept of vertex connectivity. Let

S

be a nonempty set of vertices of

G

, a collection

T_{1}, T_{2}, ..., T_{r}

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

k

-connectivity

k a p p a_{k} (G)

of

G

is the greatest positive integer

r

for which

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) = k a p p a (G)

is the connectivity of

G

. Sabidussi showed that

k a p p a (G B o x H) g e q k a p p a (G) + k a p p a (H)

for any two connected graphs

G

and

H

. In this paper, we first study the 3-connectivity of the Cartesian product of a graph

G

and a tree

T

, and show that

(i)

if

k a p p a_{3} (G) = k a p p a (G) g e q 1

, then

k a p p a_{3} (G B o x T) g e q k a p p a_{3} (G)

;

(i i)

if

1 l e q k a p p a_{3} (G) < k a p p a (G)

, then

k a p p a_{3} (G B o x T) g e q k a p p a_{3} (G) + 1

. Furthermore, for any two connected graphs

G

and

H

with

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

, if

k a p p a (G) > k a p p a_{3} (G)

, then

k a p p a_{3} (G B o x H) g e q k a p p a_{3} (G) + k a p p a_{3} (H)

; if

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

, then

k a p p a_{3} (G B o x H) g e q k a p p a_{3} (G) + k a p p a_{3} (H) - 1

. Our result could be seen as a generalization of Sabidussi's result. Moreover, all the bounds are sharp.

Recommendations

Cited in

(45)

This page was built for publication: The generalized 3-connectivity of Cartesian product

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5403014)