n-double图的连通性

Connectivity of n-double Graphs

设G_1=(V_1,E_1),G_2=(V_2,E_2)是两个连通图,直积(direct product)(也称为Kronecker product,tensor product和cross product)G_1G_2的点集为V(G_1G_2)=V(G_1)V(G_2),边集为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)).简单图G的n-double图D_n[G]=GT_n,其中n个点的全关系图T_n是完全图K_n在每个点加上一个自环得到的图.在本文中,我们研究了D_n[G]的(边)连通性,超(边)连通性.

Let G = （V, E） be a connected graph. The direct product （also named Kro-necker product, tensor product and cross product） G1 × G2 has vertex set V（G1 × G2） = V（G1） × V（G2） and edge set E（G1 × G2） = {（u1, v1）（u2, v2） ： u1 u2 ∈E（G1）, v1 v2 ∈ E（G2）}. We define the n-double of a simple graph G as the graph Dn[G] = G × Tn. The total graph Tn on n vertices is the graph associated to the total relation （where every vertex is adjacent to every vertex）. It can be obtained from the complete graph Kn by adding a loop to every vertex. In this paper, we study the （edge）connectivity, super （edge）connectivity of Dn [G].