Mixed connectivity of Cartesian graph products and bundles.

Abstract: Mixed connectivity is a generalization of vertex and edge connectivity. A graph is

(p, 0)

-connected,

p > 0

, if the graph remains connected after removal of any

p - 1

vertices. A graph is

(p, q)

-connected,

p g e q 0

,

q > 0

, if it remains connected after removal of any

p

vertices and any

q - 1

edges. Cartesian graph bundles are graphs that generalize both covering graphs and Cartesian graph products. It is shown that if graph

F

is

(p_{F}, q_{F})

-connected and graph

B

is

(p_{B}, q_{B})

-connected, then Cartesian graph bundle

G

with fibre

F

over the base graph

B

is

(p_{F} + p_{B}, q_{F} + q_{B})

-connected. Furthermore, if

q_{F}, q_{B} > 0

, then

G

is also

(p_{F} + p_{B} + 1, q_{F} + q_{B} - 1)

-connected. Finally, let graphs

G_{i}, i = 1, ..., n,

be

(p_{i}, q_{i})

-connected and let

k

be the number of graphs with

q_{i} > 0

. The Cartesian graph product

G = G_{1} B o x G_{2} B o x ... B o x G_{n}

is

(s u m p_{i}, s u m q_{i})

-connected, and, for

k g e q 1

, it is also

(s u m p_{i} + k - 1, s u m q_{i} - k + 1)

-connected.

Recommendations

Cited in

(2)

This page was built for publication: Mixed connectivity of Cartesian graph products and bundles.