The total chord length of maximal outerplanar graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911843582214144 |
|---|---|
| author | Broadus, Haley Pavelescu, Elena |
| author_facet | Broadus, Haley Pavelescu, Elena |
| contents | We consider embeddings of maximal outerplanar graphs whose vertices all lie on a cycle $\mathcal{C}$ bounding a face. Each edge of the graph that is not in $\mathcal{C}$, a chord, is assigned a length equal to the length of the shortest path in $\mathcal{C}$ between its endpoints. We define the total chord length of a graph as the sum of lengths of all its chords. For each order $n\ge 5$, we find outerplanar graphs whose total chord length is minimal among all graphs of the same order, and graphs whose total chord length is maximal among all graphs of the same order. We give a complete characterization of those graphs whose total chord length is maximal. We show that every integer value in the interval determined by the minimum and maximum values is the total chord length of a maximal outerplanar graph of the same order. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_11028 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The total chord length of maximal outerplanar graphs Broadus, Haley Pavelescu, Elena Combinatorics 05C10, 05C85 We consider embeddings of maximal outerplanar graphs whose vertices all lie on a cycle $\mathcal{C}$ bounding a face. Each edge of the graph that is not in $\mathcal{C}$, a chord, is assigned a length equal to the length of the shortest path in $\mathcal{C}$ between its endpoints. We define the total chord length of a graph as the sum of lengths of all its chords. For each order $n\ge 5$, we find outerplanar graphs whose total chord length is minimal among all graphs of the same order, and graphs whose total chord length is maximal among all graphs of the same order. We give a complete characterization of those graphs whose total chord length is maximal. We show that every integer value in the interval determined by the minimum and maximum values is the total chord length of a maximal outerplanar graph of the same order. |
| title | The total chord length of maximal outerplanar graphs |
| topic | Combinatorics 05C10, 05C85 |
| url | https://arxiv.org/abs/2404.11028 |