Complete polyhedral description of chemical graphs of maximum degree at most 3
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909870497726464 |
|---|---|
| author | Dusollier, Valentin Bonte, Sébastien Devillez, Gauvain Hertz, Alain Mélot, Hadrien Schindl, David |
| author_facet | Dusollier, Valentin Bonte, Sébastien Devillez, Gauvain Hertz, Alain Mélot, Hadrien Schindl, David |
| contents | Chemical graphs are simple undirected connected graphs, where vertices represent atoms in a molecule and edges represent chemical bonds. A degree-based topological index is a molecular descriptor used to study specific physicochemical properties of molecules. Such an index is computed from the sum of the weights of the edges of a chemical graph, each edge having a weight defined by a formula that depends only on the degrees of its endpoints. Given any degree-based topological index and given two integers $n$ and $m$, we are interested in determining chemical graphs of order $n$ and size $m$ that maximize or minimize the index. Focusing on chemical graphs with maximum degree at most 3, we show that this reduces to determining the extreme points of a polytope that contains at most 10 facets. We also show that the number of extreme points is at most 16, which means that for any given $n$ and $m$, there are very few different classes of extremal graphs, independently of the chosen degree-based topological index. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19768 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complete polyhedral description of chemical graphs of maximum degree at most 3 Dusollier, Valentin Bonte, Sébastien Devillez, Gauvain Hertz, Alain Mélot, Hadrien Schindl, David Combinatorics Discrete Mathematics Chemical graphs are simple undirected connected graphs, where vertices represent atoms in a molecule and edges represent chemical bonds. A degree-based topological index is a molecular descriptor used to study specific physicochemical properties of molecules. Such an index is computed from the sum of the weights of the edges of a chemical graph, each edge having a weight defined by a formula that depends only on the degrees of its endpoints. Given any degree-based topological index and given two integers $n$ and $m$, we are interested in determining chemical graphs of order $n$ and size $m$ that maximize or minimize the index. Focusing on chemical graphs with maximum degree at most 3, we show that this reduces to determining the extreme points of a polytope that contains at most 10 facets. We also show that the number of extreme points is at most 16, which means that for any given $n$ and $m$, there are very few different classes of extremal graphs, independently of the chosen degree-based topological index. |
| title | Complete polyhedral description of chemical graphs of maximum degree at most 3 |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2506.19768 |