Regular graphs with maximum forest number

Abstract

Punnim proved in [6] that if G is an r-regular graph of order n, then its forest number is at most c, where (Equation Presented) He also proved that the bound is sharp. Let R(rn; c) be the class of all r-regular graphs of order n. We prove in this paper that if G, H ∈ R(rn; c), then there exists a sequence of switchings σ1, σ2,. .., σt such that for each i=1, 2,...,t, and G σ1σ2...σi ∈ R(rn; c) and H = G σ1σ2...σt. © 2011 Springer-Verlag.