| Popis: |
The main goal of this paper is to enumerate planar graphs subject to a condition on the minimum degree δ. Asking for δ ≥ 1 is not very interesting, since a random planar graph only contains a constant number of isolated vertices. The condition δ ≥ 2 is directly related to the concept of the core of a graph. Given a connected graph G, its core (also called 2-core in the literature) is the maximum subgraph C with minimum degree at least two. The core C is obtained from G by repeatedly removing vertices of degree one. Conversely, G is obtained by attaching rooted trees at the vertices of C. The kernel of G is obtained by replacing each maximal path of vertices of degree two in C by a single edge. The kernel has minimum degree at least three, and C can be recovered from K by replacing edges by paths. As shown in the figure below, the kernel may have loops and multiple edges, which must be taken into account since our goal is to analyze simple graphs. Another difficulty is that when replacing loops and multiple edge by paths the same graph can be produced several times. To this end we weight multigraphs appropriately according to the number of loops and edges of each multiplicity. We remark that the concepts of core and kernel of a graph are instrumental in the theory of random graphs [3,5]. |
