All Graphs with at most 8 nodes are 2-interval-PCGs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915920696311808 |
|---|---|
| author | Calamoneri, Tiziana Monti, Angelo Petroni, Fabrizio |
| author_facet | Calamoneri, Tiziana Monti, Angelo Petroni, Fabrizio |
| contents | A graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k, then we call the graph a k-interval-PCG; in symbols, G = k-interval-PCG (T, I1, . . . , Ik). It is known that 2-interval-PCGs do not contain all graphs and the smallest known graph outside this class has 135 nodes. Here we prove that all graphs with at most 8 nodes are 2-interval-PCGs, so doing one step towards the determination of the smallest value of n such that there exists an n node graph that is not a 2-interval-PCG. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_13844 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | All Graphs with at most 8 nodes are 2-interval-PCGs Calamoneri, Tiziana Monti, Angelo Petroni, Fabrizio Discrete Mathematics Combinatorics A graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k, then we call the graph a k-interval-PCG; in symbols, G = k-interval-PCG (T, I1, . . . , Ik). It is known that 2-interval-PCGs do not contain all graphs and the smallest known graph outside this class has 135 nodes. Here we prove that all graphs with at most 8 nodes are 2-interval-PCGs, so doing one step towards the determination of the smallest value of n such that there exists an n node graph that is not a 2-interval-PCG. |
| title | All Graphs with at most 8 nodes are 2-interval-PCGs |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2202.13844 |