The number of connected sparsely edged graphs. II. Smooth graphs and blocks

✍ Scribed by E. M. Wright

• Publisher: John Wiley and Sons
• Year: 1978
• Tongue: English
• Weight: 215 KB
• Volume: 2
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190020403

✦ Synopsis

A smooth graph is a connected graph without endpoints; f (n, q ) is the number of connected graphs, v(n, q ) is the number of smooth graphs, and u(n, q) is the number of blocks on n labeled points and q edges: wk, V,, and u k are the exponential generating functions of f(n, n + k ) , v(n, n + k). and u(n, n + k), respectively. For any k a 1, our reduction method shows that v k can be deduced at once from wk, which was found for successive k by the computer method described in our previous paper. Again the reduction method shows that Uk must be a sum of powers (mostly negative) of 1 -X and, given this information, we develop a recurrence method well suited to calculate Uk for successive k. Exact formulas for v(n, n + k ) and u(n, n + k ) for general n follow at once.

SMOOTH GRAPHS

We use the notation of Ref. 4, except where we specifically vary it. Our aim here is to find formulas for general n and particular k for v ( n , n + k ) , the number of "smooth" labeled (n, n + k ) graphs (i.e., connected graphs without endpoints), and for u(n, n + k), the number of labeled (n, n + k ) blocks. Clearly u(n, n + k) = 0 (k <O), v(n, n ) = ( n -1)!/2