The Pfaffian property of graphs is of fundamental importance in graph theory,as it precisely characterizes those graphs for which the number of perfect matchings can be computed in polynomial time with respect to the ...The Pfaffian property of graphs is of fundamental importance in graph theory,as it precisely characterizes those graphs for which the number of perfect matchings can be computed in polynomial time with respect to the number of edges.The study of Pfaffian graphs originated from the enumeration of perfect matching in planar graphs.References[5,6,8]demonstrated that every planar graph is Pfaffian.Therefore,the Pfaffian property and planarity of graphs play a vital role in modern matching theory.This paper contributes a complete characterization of the Pfaffian property and planarity of connected Cayley graphs over the dicyclic group T_(4n) of order 4n(n≥3),shows that the Cayley graph Cay(T_(4n),S)is Pfaffian if and only if n is odd and S={a^(k_(1)),a^(2n−k_(1)),ba^(k_(2)),ba^(n+k_(2))},where 1≤k_(1)≤n−1,0≤k_(2)≤n−1 and(k_(1),n)=1,and furthermore,shows that Cay(T4n,S)is never planar.展开更多
基金supported by NSFC(No.12201202)NSF of Hunan Province(No.2023JJ30180)NSFC(No.12471022)。
文摘The Pfaffian property of graphs is of fundamental importance in graph theory,as it precisely characterizes those graphs for which the number of perfect matchings can be computed in polynomial time with respect to the number of edges.The study of Pfaffian graphs originated from the enumeration of perfect matching in planar graphs.References[5,6,8]demonstrated that every planar graph is Pfaffian.Therefore,the Pfaffian property and planarity of graphs play a vital role in modern matching theory.This paper contributes a complete characterization of the Pfaffian property and planarity of connected Cayley graphs over the dicyclic group T_(4n) of order 4n(n≥3),shows that the Cayley graph Cay(T_(4n),S)is Pfaffian if and only if n is odd and S={a^(k_(1)),a^(2n−k_(1)),ba^(k_(2)),ba^(n+k_(2))},where 1≤k_(1)≤n−1,0≤k_(2)≤n−1 and(k_(1),n)=1,and furthermore,shows that Cay(T4n,S)is never planar.
