Associate Professor Yuqing Lin

The anti-forcing number of a connected graph G is the smallest number of edges such that the remaining graph obtained by deleting these edges has a unique perfect matching. In this paper, we show that the anti-forcing number of every fullerene has at least four. We give a procedure to construct all fullerenes whose anti-forcing numbers achieve the lower bound four. Furthermore, we show that, for every even n = 20 (n 6= 22; 26), there exists a fullerene with n vertices that has the anti-forcing number four, and the fullerene with 26 vertices has the anti-forcing number five.

© 2017 Elsevier B.V. Diagnosability is a significant metric to measure the reliability of multiprocessor systems. In 2012, a new measure for fault tolerance of the system was proposed by Peng et al. This measure is called the g-good-neighbor diagnosability that restrains every fault-free node to contain at least g fault-free neighbors. The Cayley graph CKn generated by the complete graph Kn has many good properties as other Cayley graphs. In this paper, we show that the connectivity of CKn is n(n-1)2, the 1-good-neighbor connectivity of CKn is n2-n-2 and the 1-good-neighbor diagnosability of CKn under the PMC model is n2-n-1 for n=4 and under the MM* model is n2-n-1 for n=5.

A (k, g)-cage is a graph that has the least number of vertices among all k-regular graphs with girth g. It has been conjectured (Fu et al. in J. Graph Theory, 24:187-191, 1997) that all (k, g)-cages are k-connected for every k = 3. A k-connected graph G is called superconnected if every k-cutset S is the neighborhood of some vertex. Moreover, if G-S has precisely two components, then G is called tightly superconnected. In this paper, we prove that every (4, g)-cage is tightly superconnected when g = 11 is odd. © 2011 Springer.