Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians

CORC > 厦门大学 > 数学科学－已发表论文

	Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians
	Yan, WG ; Zhang, FJ ; Zhang FJ(张福基)
刊名	http://dx.doi.org/10.1016/S0196-8858(03)00097-6
	2004-05
关键词	MOLECULAR-ORBITALS
英文摘要	The Pfaffian method enumerating perfect matchings of plane graphs was discovered by Kasteleyn. We use this method to enumerate perfect matchings in a type of graphs with reflective symmetry which is different from the symmetric graphs considered in [J. Combin. Theory Ser. A 77 (1997) 67, MATCH-Commun. Math. Comput. Chem. 48 (2003) 117]. Here are some of our results: (1) If G is a reflective symmetric plane graph without vertices on the symmetry axis, then the number of perfect matchings of G can be expressed by a determinant of order \G\/2, where \G\ denotes the number of vertices of G. (2) If G contains no subgraph which is, after the contraction of at most one cycle of odd length, an even subdivision of K?,3, then the number of perfect matchings of G x K-2 can be expressed by a determinant of order \G\. (3) Let G be a bipartite graph without cycles of length 4s, is an element of G {1, 2....}. Then the number of perfect matchings of G x K-2 equals Pi(I + theta(2))(mtheta), where the product ranges over all non-negative eigenvalues theta of G and m(theta) is the multiplicity of eigenvalue theta. Particularly, if T is a tree then the number of perfect matchings of T x K-2 equals Pi(1+ theta(2))(mtheta), where the product ranges over all non-negative eigenvalues theta of T and m(theta) is the multiplicity of eigenvalue theta. (C) 2003 Elsevier Inc. All rights reserved.
语种	英语
内容类型	期刊论文
源URL	[http://dspace.xmu.edu.cn/handle/2288/66340]
专题	数学科学－已发表论文
推荐引用方式 GB/T 7714	Yan, WG,Zhang, FJ,Zhang FJ. Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians[J]. http://dx.doi.org/10.1016/S0196-8858(03)00097-6,2004.
APA	Yan, WG,Zhang, FJ,&张福基.(2004).Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians.http://dx.doi.org/10.1016/S0196-8858(03)00097-6.
MLA	Yan, WG,et al."Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians".http://dx.doi.org/10.1016/S0196-8858(03)00097-6 (2004).