New Formulae for the Decycling Number of Graphs

Abstract

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 ∇(G). Our results include: (a) For any graph G,, where T is taken over all the spanning trees of G and α(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, where β(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 ∇-set if and only if m(S) is minimum, where∇-set denotes a decycling set containing exactly ∇(G) vertices of G. This provides a new way to locate ∇(G) for k-regular graphs G. (c) 4-regular graphs G with the decycling number are determined.

Keywords

• decycling number
• independence number
• cycle rank
• margin number
• 05c07
• 05c38