科研之友
微信
新浪微博
Facebook
分享链接
摘要
A set S of vertices of a graph G is called a decycling set if G - S is acyclic. The minimum order of a decycling set is called the decycling number of G, and denoted by del(G). Our results include: (a) For any graph G, @@@ del(G) = n - mpx(T){alpha(G - E(T))}, @@@ where T is taken over all the spanning trees of G and alpha(G - E(T)) is the independence number of the co-tree G - E(T). This formula implies that computing the decycling number of a graph G is equivalent to finding a spanning tree in G such that its co-tree has the largest independence number. Applying the formula, the lower bounds for the decycling number of some (dense) graphs may be obtained. (b) For any decycling set S of a k-regular graph G, @@@ |S| = 1/k-1(beta(G) + m(S)), @@@ where beta(G) = |E(G)|-|V(G)|+1 and m(S) = c +|E(S)| - 1, c and |E(S)| are, respectively, the number of components of G - S and the number of edges in G[S]. Hence S is a del-set if and only if m(S) is minimum, where del-set denotes a decycling set containing exactly del(G) vertices of G. This provides a new way to locate del(G) for k-regular graphs G.
