On the Asymptotic Enumeration of Labeled Connected k-Cyclic Graphs without Bridges

摘要

We consider undirected simple connected graphs. A outpoint of a connected graph is a vertex such that, after the deletion of this vertex together with the edges incident to it, the graph becomes disconnected. A block is a connected graph without cutpoints or a maximal connected nontrivial subgraph without cutpoints. A bridge in a connected graph is an edge such that removing it makes the graph disconnected. The cyclomatic number of a connected graph equals the difference between the number of edges and the number of vertices in the graph plus 1. A k-cyclic graph is a graph whose cyclomatic number equals k. Hanlon and Robinson [1] enumerated both unlabeled and labeled graphs without bridges. For the generating function of a labeled graph, they obtained a functional-differential equation and a nonlinear partial differential equation. However, their formulas have not been reduced to a form convenient for calculation. Probably, this is the reason why Sloane's classical The On-Line Encyclopedia of Integer Sequences [2] contains no data on the number of labeled graphs without bridges (that is, 2-edge-connected graphs).