Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427752 | Information Processing Letters | 2012 | 4 Pages |
Let G1G1 and G2G2 be two graphs. The Kronecker product G1×G2G1×G2 has vertex set V(G1×G2)=V(G1)×V(G2)V(G1×G2)=V(G1)×V(G2) and edge set E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1)E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1) and v1v2∈E(G2)}v1v2∈E(G2)}. A graph G is super connected, or simply super-κ, if every minimum separating set is the neighbors of a vertex of G, that is, every minimum separating set isolates a vertex. In this paper we show that if G is a graph with κ(G)=δ(G)κ(G)=δ(G) and KnKn(n⩾3)(n⩾3) a complete graph on n vertices, except that G is a complete bipartite graph Km,mKm,m (m⩾1m⩾1) and Kn=K3Kn=K3, then G×KnG×Kn is super-κ , where κ(G)κ(G) and δ(G)δ(G) are the connectivity and the minimum degree of G, respectively.
► We present the super connectivity on the Kronecker product of two graphs. ► The Kronecker product of a nonbipartite graph and a complete graph is super-k. ► The Kronecker product of a bipartite graph and a complete graph is super-k.