Enumeration of labeled,connected, homeomorphically irreducible graphs

Translated from Matematicheskie Zametki, Vol. 49, No. 3, pp. 12–22, March, 1991.     

Enumeration of labeled connected graphs with given order and size

We deduce a new formula for the number of labeled connected graphs with given order and number of edges in terms of the block generating function. Applying this formula, we exactly and asymptotically enumerate cacti with given order and cyclomatic number.     

Enumeration of connected graph coverings

The number of the isomorphism classes of n-fold coverings of a graph G is enumerated by the authors (Canad. J. Math. XLII (1990), 747–761) and Hofmeister (Discrete Math. 98 (1991), 175–183). But the enumeration of the isomorphism classes of connected n-fold coverings of a graph has not been studied except for n = 2. In this paper, we enumerate the isomorphism classes of connected n-fold coverings of a graph G for any n. As a consequence, we obtain a formula for finding the total number of conjugacy classes of subgroups of a given index of a finitely generated free group. © 1996 John Wiley & Sons, Inc.     

Enumeration of difference graphs

A difference graph is a bipartite graph G = (X, Y; E) such that all the neighborhoods of the vertices of X are comparable by inclusion. We enumerate labeled and unlabeled difference graphs with or without a bipartition of the vertices into two stable sets. The labeled enumerations are expressed in terms of combinatorial numbers related to the Stirling numbers of the second kind.     

Enumeration of point-determining graphs

Point-determining graphs are graphs in which no two vertices have the same neighborhoods, co-point-determining graphs are those whose complements are point-determining, and bi-point-determining graphs are those both point-determining and co-point-determining. Bicolored point-determining graphs are point-determining graphs whose vertices are properly colored with white and black. We use the combinatorial theory of species to enumerate these graphs as well as the connected cases.     

Enumeration of ladder graphs

Consider N points labelled cyclically forming the vertex set of a planar convex polygon, pairs of which may be connected by bonds. Define a ladder graph to be a graph with no crossing bonds. New simple proofs are given for two results of Kirkman relating to the total number of ladder graphs with A bonds. Relations are derived for calculating the number of connected ladder graphs with A bonds, and asymptotic expressions are obtained.     

Enumeration of labeled block-cactus graphs

The exact and asymptotic formulas are obtained for the number of block-cactus graphs and Eulerian block-cactus graphs with a given number of vertices.     

Completely connected clustered graphs

Planar drawings of clustered graphs are considered. We introduce the notion of completely connected clustered graphs, i.e., hierarchically clustered graphs that have the property that not only every cluster but also each complement of a cluster induces a connected subgraph. As a main result, we prove that a completely connected clustered graph is c-planar if and only if the underlying graph is planar. Further, we investigate the influence of the root of the inclusion tree to the choice of the outer face of the underlying graph and vice versa.     

On spanning connected graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if the set of the vertices of all the paths in C(u,v) contains all the vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k^*-connected graphs.     

On path connected graphs

Given n and i, n > 2, 2 ≤ i ≤ n ? 1, the smallest size of an n-graph without endvertices is obtained, which ensures a path of length i between any two vertices of the graph.     

Counting connected graphs asymptotically

We find the asymptotic number of connected graphs with k vertices and k−1+l edges when k,l approach infinity, re-proving a result of Bender, Canfield and McKay. We use the probabilistic method, analyzing breadth-first search on the random graph G(k,p) for an appropriate edge probability p. Central is the analysis of a random walk with fixed beginning and end which is tilted to the left.     

Enumeration of labeled,three-connected graphs

The technique of functional Legendre transformations developed in statistical physics and quantum field theory is used to enumerate labeled graphs and multi-graphs.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 120, pp. 21–24, 1982.     

Enumeration of graphs by degree sequence

The degree sequence (d₀, d₁, …, d_p-1) of a graph G of order p is defined by d_k = the number of points of G of degree k. Methods of Robinson are extended to produce a generating function F(x₀, x₁, x₂, …) where the coefficient of x…x is the number of graphs of order p having degree sequence (d₀, …, d_p-1).     

Enumeration of non-positive planar trivalent graphs

In this paper we construct inverse bijections between two sequences of finite sets. One sequence is defined by planar diagrams and the other by lattice walks. In [13] it is shown that the number of elements in these two sets are equal. This problem and the methods we use are motivated by the representation theory of the exceptional simple Lie algebra G ₂. However in this account we have emphasised the combinatorics.     

Enumeration of simple complete topological graphs

A simple topological graph T=(V(T),E(T)) is a drawing of a graph in the plane, where every two edges have at most one common point (an end-point or a crossing) and no three edges pass through a single crossing. Topological graphs G and H are isomorphic if H can be obtained from G by a homeomorphism of the sphere, and weakly isomorphic if G and H have the same set of pairs of crossing edges. We prove that the number of isomorphism classes of simple complete topological graphs on n vertices is 2^Θ(n4). We also show that the number of weak isomorphism classes of simple complete topological graphs with n vertices and crossings is at least 2^{n(logn−O(1))}, which improves the estimate of Harborth and Mengersen.