|
Applied Graph Theory
An asymptotics for the number of labelled planar tetracyclic and pentacyclic graphs
V. A. Voblyi Russian Institut for Scientific and Technical Information, Moscow, Russia
Abstract:
A connected graph with a cyclomatic number $k$ is said to be a $k$-cyclic graph. We obtain the formula for the number of labelled non-planar pentacyclic graphs with a given number of vertices, and find the asymptotics of the number of labelled connected planar tetracyclic and pentacyclic graphs with $n$ vertices as $n\to\infty$. We prove that under a uniform probability distribution on the set of graphs under consideration, the probability that the labelled tetracyclic graph is planar is asymptotically equal to 1089/1105, and the probability that the labeled pentacyclic graph is planar is asymptotically equal to 1591/1675.
Keywords:
labelled graph, planar graph, tetracyclic graph, pentacyclic graph, block, enumeration, asymptotics, probability.
Citation:
V. A. Voblyi, “An asymptotics for the number of labelled planar tetracyclic and pentacyclic graphs”, Prikl. Diskr. Mat., 2023, no. 59, 72–79
Linking options:
https://www.mathnet.ru/eng/pdm794 https://www.mathnet.ru/eng/pdm/y2023/i1/p72
|
|