Connectivity of Kronecker products by K₂

Abstract: Let

k a p p a (G)

be the connectivity of

G

. The Kronecker product

G_{1} i m e s G_{2}

of graphs

G_{1}

and

G_{2}

has vertex set

V (G_{1} i m e s G_{2}) = V (G_{1}) i m e s V (G_{2})

and edge set

E (G_{1} i m e s G_{2}) = (u_{1}, v_{1}) (u_{2}, v_{2}) : u_{1} u_{2} i n E (G_{1}), v_{1} v_{2} i n E (G_{2})

. In this paper, we prove that

k a p p a (G i m e s K_{2}) = e x t u p m i n 2 k a p p a (G), e x t u p m i n | X | + 2 | Y |

, where the second minimum is taken over all disjoint sets

X, Y s u b s e t e q V (G)

satisfying (1)

G - (X c u p Y)

has a bipartite component

C

, and (2)

G [V (C) c u p x]

is also bipartite for each

x i n X

.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Connectivity of Kronecker products by \(K_2\)