کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427752 | 686551 | 2012 | 4 صفحه PDF | دانلود رایگان |
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.
Journal: Information Processing Letters - Volume 112, Issue 10, 31 May 2012, Pages 402–405