Parts | Days | Selection | Search | Updates | Downloads | Help

SOE: Fachverband Physik sozio-ökonomischer Systeme

SOE 4: Poster

SOE 4.6: Poster

Monday, March 27, 2023, 17:00–19:00, P2/OG2

Counting Graphs and Molecules — •Rana Shojaei^1,2,3 and Thilo Gross^1,2,3 — ¹Helmholtz Institute for Functional Marine Biodiversity at the University of Oldenburg (HIFMB), Oldenburg, Germany — ²Alfred Wegener Institute- Helmholtz Centre for Marine and Polar Research, Bremerhaven, Germany — ³Carl von Ossietzky University- Institute for Chemistry and Biology of the Marine Environment (ICBM), Oldenburg, Germany

Counting the number of simple graphs that can be constructed between a given number of unlabeled (indistinguishable) nodes is a long-standing challenge. We consider this problem using Polya's counting theory. For illustration, we first consider a related problem that has historically received much attention: counting the number of chemical molecules with a given number of atoms. Indeed, it was in the context of this problem that the term 'graph' was first coined. Application of the same principles and procedure leads to a simple closed-form formula for the number of simple graphs, however, the efficient evaluation of the formula for large graphs remains an open problem.