Publication: Decycling regular graphs
1
0
Issued Date
2005
Resource Type
File Type
application/pdf
ISSN
10344942
Other identifier(s)
2-s2.0-27944488332
Rights Holder(s)
Scopus
Bibliographic Citation
Australasian Journal of Combinatorics. Vol 32, (2005), p.147-162
Suggested Citation
Punnim N. Decycling regular graphs. Australasian Journal of Combinatorics. Vol 32, (2005), p.147-162. Retrieved from: https://hdl.handle.net/20.500.14740/6013
Author(s)
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.