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

Supereulerian graphs in generalized prisms and complementary prisms

作　　者：王刘岩 牛兆宏 

机构地区：[1]山西大学数学科学学院,山西太原030006

出　　处：《云南民族大学学报（自然科学版）》2017年第5期376-380,共5页Journal of Yunnan Minzu University:Natural Sciences Edition

基　　金：国家自然科学基金(11501341;11401353;11671296)

摘　　要：对于一个图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.

关 键 词：广义棱柱 补棱柱 超欧拉图 可折图 

分 类 号：O157.5[理学—数学]