Kronecker乘积图的平面性

On Planarity of Kronecker Product of Graphs

设G1和G2是两个连通图,则G1和G2的Kronecker积G1×C2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.该文证明了如果G=G1×G2是平面图并且︱Gi︱≥3,那么G1和G2都是平面图;还完全确定了Pn×G2的平面性,n=3,4.

Let G1 and G2 be two connected graphs .The Kronecker product G1 × G2 is the graph with vertex set V (G1 × G2 )=V (G1 ) × V (G2 ) and the edge set E(G1 × G2 )={(u1 ,v1 )(u2 ,v2 )∶ u1 u2∈ E(G1 ) ,v1 v2 ∈ E(G2 )} .We consider the planarity of G1 × G2 .In particular ,we totally determine that w hen Pn × G2 is plallar ,n=2 ,3 .