Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Forbidden subgraphs in connected graphs
Ravelomanana V., Thimonier L. Theoretical Computer Science314 (1):121-171,2004.Type:Article
Date Reviewed: Jun 30 2004

This is a long and technical paper on graphical enumeration for connected graphs (and multigraphs) with n vertices and n+k edges. Let Gn,k denote such a graph. The technique used is that of formal exponential generating series. The main contribution of the paper is a proof that almost all connected Gn,k for n,k → ∞ and k = o(n1/3) are triangle-free. In fact, Corollary 32 gives more detailed information on the number of such graphs. The proof makes use of a long chain of lemmas, chiefly devoted to obtaining bounds on coefficients of various generating formal series, and making heavy use of the fundamental fact, first demonstrated in detail by E.M. Wright, that many exponential generating series used in graphical enumeration are expressible as rational series in the tree enumerating series. The enumeration information is extracted from the leading terms of series of this type.

The lemmas use three kinds of arguments: upper or lower bounding of coefficients; surgery on graphs; and analytic estimation, namely, the saddle point method. The surgery on graphs argument consists of identifying small subgraph structures and blowing up vertices to trees, or contracting trees to vertices. These surgeries establish connections to integer partitioning. The ultimate object of the paper is to obtain enumerative asymptotics for connected graphs with k = o(n1/3) that exclude any given family of subgraphs. However, the arguments are already so intricate for triangle exclusion that some form of mechanization through a computer algebra system would be needed for any serious extension of the results. Recently, Flajolet, Salvy, and Schaeffer announced a purely analytic representation for the generating series for Gn,k, n,k arbitrary. This means, at least, that many of the coefficient-by-coefficient bounding arguments needed when using formal series may be avoidable.

Reviewer:  Bruce Litow Review #: CR129831 (0501-0077)
Bookmark and Share
  Reviewer Selected
 
 
Combinatorial Algorithms (G.2.1 ... )
 
 
Generating Functions (G.2.1 ... )
 
 
Graph Labeling (G.2.2 ... )
 
 
Combinatorics (G.2.1 )
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Combinatorial Algorithms": Date
The complexity of combinatorial problems with succinct input representation
Wagner K. (ed) Acta Informatica 23(3): 325-356, 1986. Type: Article
Dec 1 1988
An optimal algorithm for parallel selection
Akl S. Information Processing Letters 19(1): 47-50, 1984. Type: Article
Nov 1 1985
A performance guarantee for the greedy set-partitioning algorithm
E G. J., Langston M. Acta Informatica 21(4): 409-415, 1984. Type: Article
May 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