Decycling regular graphs

Abstract

For a graph G and S ⊆ V(G), if G - S is acyclic, then S is said to be a decycling set of G. The cardinality of the smallest decycling set of G is called the decycling number of G and is denoted by φ(G). We prove in this paper that if G runs over the set of graphs with a fixed degree sequence d, then the values φ(G) completely cover a line segment [a, b] of positive integers. Let R(d) be the class of all graphs having degree sequence d. For an arbitrary graphic degree sequence d, two invariants a:= min(φ,d) = min{φ(G): G ∈ R(d)} and b:= max(φ, d) = max{φ(G): G ∈ R(d)}, arise naturally. For a regular graphic degree sequence d = rn:= (r, r,..., r), where r is the vertex degree and n is the order of the graph, the exact value of min(φ, rn) and max(φ, rn) are found in all situations. As an application, we can find all cubic graphs of order 2n having the smallest decycling number.