New Formulae for the Decycling Number of Graphs

Yang, Chao  ; Ren, Han

Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 125-141

Résumé

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, ∇ (G) = n - max_T {α (G- E(T)) },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, |S| = 1/k-1 (β (G) + m(S)),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 ∇ (G) = β(G)3 are determined.

Détail

Keywords: decycling number, independence number, cycle rank, margin number