RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2020 Number 50, Pages 87–92 (Mi pdm724)

This article is cited in 1 paper

Applied Graph Theory

Enumeration of labeled Eulerian pentacyclic graphs

V. A. Voblyi

All-Russian Institut for Scientific and Technical Information, Moscow, Russia

Abstract: An Euler graph is a connected graph in which all degrees of vertices are even numbers. A pentacyclic graph is a connected graph with $n$ vertices and $n + 4$ edges. We obtain an explicit formula for the number of labeled Euler pentacyclic graphs with a given number of vertices, and found the corresponding asymptotics for the number of such graphs with a large number of vertices. We prove that, given a uniform probability distribution, the probability that a labeled pentacyclic Euler graph is a block (cactus) is asymptotically $53/272$ ($63/272$), respectively.

Keywords: labeled graph, Eulerian graph, pentacyclic graph, block, enumeration, asymptotics, probability.

UDC: 519.175.3

DOI: 10.17223/20710410/50/6



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025