A {(3,4), 4}-fullerene graph S is a 4-regular map on the sphere whose faces are of length 3 or 4.It follows from Euler s formula that the number of triangular faces is eight.A set H of disjoint quadrangular faces of S...A {(3,4), 4}-fullerene graph S is a 4-regular map on the sphere whose faces are of length 3 or 4.It follows from Euler s formula that the number of triangular faces is eight.A set H of disjoint quadrangular faces of S is called resonant pattern if S has a perfect matching M such that every quadrangular face in H is M-alternating.Let k be a positive integer,S is k-resonant if any i≤k disjoint quadrangular faces of S form a resonant pattern.Moreover,if graph S is k-resonant for any integer k,then S is called maximally resonant.In this paper,we show that the maximally resonant{(3,4),4}-fullerene graphs are S_6,S_8,S_(10)~2,S_(12)~2,S_(12)~4,S_(12)~5,S_(14)~3,S_(14)~5,S_(16)~3,S_(18)~5,S_(24) as shown in Fig.1.As a corollary,it is shown that if a {(3,4),4}-fullerene graph is 4-resonant,then it is also maximally resonant.展开更多
限制性支撑树最大容量扩张问题(the maximum capacity expansion of spanning tree problem with constraints,MCESTC)是NP-难问题。针对MCESTC问题,采用允许增加支撑树长度值的双边替换策略设计了一个启发式算法进行求解,并证明了算法...限制性支撑树最大容量扩张问题(the maximum capacity expansion of spanning tree problem with constraints,MCESTC)是NP-难问题。针对MCESTC问题,采用允许增加支撑树长度值的双边替换策略设计了一个启发式算法进行求解,并证明了算法的正确性。最后,用实例阐述运用该算法求解问题的过程,从而验证算法的有效性。展开更多
基金Supported by NSFC(Grant Nos.11801148 and 11626089)the Foundation for the Doctor of Henan Polytechnic University(Grant No.B2014-060)。
文摘A {(3,4), 4}-fullerene graph S is a 4-regular map on the sphere whose faces are of length 3 or 4.It follows from Euler s formula that the number of triangular faces is eight.A set H of disjoint quadrangular faces of S is called resonant pattern if S has a perfect matching M such that every quadrangular face in H is M-alternating.Let k be a positive integer,S is k-resonant if any i≤k disjoint quadrangular faces of S form a resonant pattern.Moreover,if graph S is k-resonant for any integer k,then S is called maximally resonant.In this paper,we show that the maximally resonant{(3,4),4}-fullerene graphs are S_6,S_8,S_(10)~2,S_(12)~2,S_(12)~4,S_(12)~5,S_(14)~3,S_(14)~5,S_(16)~3,S_(18)~5,S_(24) as shown in Fig.1.As a corollary,it is shown that if a {(3,4),4}-fullerene graph is 4-resonant,then it is also maximally resonant.
文摘限制性支撑树最大容量扩张问题(the maximum capacity expansion of spanning tree problem with constraints,MCESTC)是NP-难问题。针对MCESTC问题,采用允许增加支撑树长度值的双边替换策略设计了一个启发式算法进行求解,并证明了算法的正确性。最后,用实例阐述运用该算法求解问题的过程,从而验证算法的有效性。