四角系统的Z-变换图的Hamilton路  

Hamilton paths in Z-transformation graphs of polyomino graphs

作　　者：魏首柳[1] 柯小玲[1] 

机构地区：[1]闽江学院数学系,福建福州350108

出　　处：《闽江学院学报》2009年第2期12-15,共4页Journal of Minjiang University

基　　金：福建省教育厅科技规划项目(JA07177);闽江学院科技育苗项目(YKY08003)(YKY07010)

摘　　要：如果G表示一个四角系统,则G的Z-变换图Z(G)指如下定义的图:图Z(G)的所有顶点对应于四角系统G中的所有完美匹配,且Z(G)中的两个顶点有一条边相连当且仅当它们在G中对应的两个完美匹配的对称差恰好形成G的一个四角形.利用图同构的方法,证明了两类四角系统(L-四角系统和Z-四角系统)的Z-变换图必含有一条Hamilton路.Let G be a polyomino graph, then the Z-transformation graph Z（G） of G is the graph where the vertices are the perfect matchings of G and where two perfect matchings are joined by an edge provided their symmetric difference is a square of G. In this paper,we prove that the Z-transformation graphs Z（G） of line chain polyomino graph and zigzag chain polyomino graph have one Hamilton path by isomorphism of graph.

关 键 词：四角系统 Z-变换图 完美匹配 HAMILTON路 

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