Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs

摘要

The Kronecker product of two connected graphs G _1,G _2, denoted by G _1 × G _2, is the graph with vertex set V(G _1 × G _2)=V(G _1)× V(G _2) and edge set E(G _1 × G _2)=(u _1,v _1)(u _2,v _2):u _1u _2∈ E(G _1),v _1v _2∈E(G _2). The kth power G ~k of G is the graph with vertex set V(G) such that two distinct vertices are adjacent in G k if and only if their distance apart in G is at most k. A connected graph G is called super-κ if every minimal vertex cut of G is the set of neighbors of some vertex in G. In this note, we consider the super-connectivity of the Kronecker products of several kinds of graphs and complete graphs. We show that D=G×K m is super-κ for m<3 and G satisfying one of the following conditions: (1) G is a non-complete split graph with |C|<5; (2) G is a power graph of a path P _n ~k such that n<2k; (3) G is a power graph of a cycle C _n ~r such that n