广义棱柱和补棱柱中的超欧拉图

Supereulerian graphs in generalized prisms and complementary prisms

对于一个图G,它的顶点标号为1,2,…,n,S_n是在{1,2,…,n}上的n次对称群,α∈S_n是一个置换,图G的α-广义棱柱,记作α(G),是指图G的2个复制,G_x和G_y,连同所有置换边(x_i,y_(α(i))(1≤i≤n)所构成的图.图G的补棱柱,记作G G,同构于由G和G的补图G的不交并,再加上一个连接G和G对应顶点的完美匹配构成的图.如果图G有一个生成欧拉子图,那么称G是超欧拉图.研究了完全二部图、路和圈的广义棱柱和补棱柱是超欧拉图的充要条件.

For a graph G with vertices labeled 1,2,丨,n,a permutation a in S_n,the symmetric group on { 1,2,丨,n},and the a-generalized prism over G,a（G）,they consist of two copies of,G say Gxand Gy,along with the edges（ x_i,y_（a（i）））. The complementary prism GG is isomorphic to the graph that arises from the disjoint union of G and the complement G of G by adding a perfect matching joining corresponding pairs of vertices in G and G. A graph is called supereulerian if it has a spanning eulerian subgraph. This paper investigates the necessary and sufficient conditions for the generalized prisms and complementary prisms of the complete bipartite graphs,paths and circles to be supereulerian graphs.