Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Large induced forests in graphs
Shi L., Xu H. Journal of Graph Theory85 (4):759-779,2017.Type:Article
Date Reviewed: Jul 30 2018

A subset S of the vertex set of a given graph G is acyclic if the subgraph of G induced by S does not consist of any cycle. The maximum order of such an acyclic set in G is denoted by a(G). The author proves three interesting theorems regarding this parameter based on the order and size of the graph G.

The first theorem states that for a connected graph G of order n and size m, a(G)≥(8n-2m-2)/9. In this result they also prove that equality occurs if and only if G consists of K4 and K5 linked by an edge.

The second theorem states that for a triangle-free graph of order n and size m, a(G)≥(20n-5m-5)/19.

According to the third theorem, for a connected planar graph G of order n and size m with girth of at least five, a(G)≥(8n-2m-2)/7, and the equality holds if and only if G is a graph belonging to the collection of polyhedrons of the form D3k+2; k=1, 2, 3, 4, 6.

Each theorem is followed by an equally interesting corollary. The proofs of all three theorems use mathematical induction techniques and progress by establishing several significant claims and facts connecting a(G) and t(G), the expression on the right-hand side of the inequalities in the given theorem. These proofs contain beautiful structural analyses and characterizations of the graphs concerned, and also involve many computational aspects. The content is presented in a systematic and remarkable manner. It is an interesting paper.

Reviewer:  Sudev Naduvath Review #: CR146178 (1810-0541)
Bookmark and Share
  Reviewer Selected
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Theory": Date
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Jan 1 1985
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy