Publication: The forest number of (n,m)-Graphs
0
0
Issued Date
2008
Resource Type
File Type
application/pdf
ISSN
3029743
Other identifier(s)
2-s2.0-70349923416
Rights Holder(s)
มหาวิทยาลัยศรีนครินทรวิโรฒ
Bibliographic Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 4535 LNCS, (2008), p.33-40
Suggested Citation
Chantasartrassmee A., Punnim N. The forest number of (n,m)-Graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 4535 LNCS, (2008), p.33-40. doi:10.1007/978-3-540-89550-3_4 Retrieved from: https://hdl.handle.net/20.500.14740/4172
Author(s)
Abstract
Let G = (V,E) be a graph and F ⊆ V. Then F is called an induced forest of G if G[F] is acyclic. The forest number, denoted by f(G), of G is defined by f(G) := max {|F| : F is an induced forest of G}. We proved that if G runs over the set of all graphs of order n and size m, then the values f(G) completely cover a line segment [x,y] of positive integers. Let ς(n,m) be the set of all graphs of order n and size m and Cς(n, m) be the subset of consisting of all connected graphs. We are able to obtain the extremal results for the forest number in the class ς(n, m) and Cς(n, m). © 2008 Springer Berlin Heidelberg.