SKM 2023 – scientific programme
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 Shojaei1,2,3 and Thilo Gross1,2,3 — 1Helmholtz Institute for Functional Marine Biodiversity at the University of Oldenburg (HIFMB), Oldenburg, Germany — 2Alfred Wegener Institute- Helmholtz Centre for Marine and Polar Research, Bremerhaven, Germany — 3Carl 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.