Wiener Index and Remoteness in Triangulations and Quadrangulations
Let $G$ be a a connected graph. The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. We provide asymptotic formulae for the maximum Wiener index of simple triangulations and quadrangulations with given connectivity, as the order increases, and ma...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/6473/pdf |
| _version_ | 1797269996571721728 |
|---|---|
| author | Éva Czabarka Peter Dankelmann Trevor Olsen László A. Székely |
| author_facet | Éva Czabarka Peter Dankelmann Trevor Olsen László A. Székely |
| author_sort | Éva Czabarka |
| collection | DOAJ |
| description | Let $G$ be a a connected graph. The Wiener index of a connected graph is the
sum of the distances between all unordered pairs of vertices. We provide
asymptotic formulae for the maximum Wiener index of simple triangulations and
quadrangulations with given connectivity, as the order increases, and make
conjectures for the extremal triangulations and quadrangulations based on
computational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic mean
of the distances from $v$ to all other vertices of $G$, then the remoteness of
$G$ is defined as the largest value of $\overline{\sigma}(v)$ over all vertices
$v$ of $G$. We give sharp upper bounds on the remoteness of simple
triangulations and quadrangulations of given order and connectivity. |
| first_indexed | 2024-04-25T01:57:15Z |
| format | Article |
| id | doaj.art-3cb09316845e432cb68ad74e62bbe952 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:15Z |
| publishDate | 2021-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-3cb09316845e432cb68ad74e62bbe9522024-03-07T15:44:09ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-03-01vol. 23 no. 1Graph Theory10.46298/dmtcs.64736473Wiener Index and Remoteness in Triangulations and QuadrangulationsÉva Czabarkahttps://orcid.org/0000-0001-8568-5552Peter DankelmannTrevor OlsenLászló A. SzékelyLet $G$ be a a connected graph. The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. We provide asymptotic formulae for the maximum Wiener index of simple triangulations and quadrangulations with given connectivity, as the order increases, and make conjectures for the extremal triangulations and quadrangulations based on computational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic mean of the distances from $v$ to all other vertices of $G$, then the remoteness of $G$ is defined as the largest value of $\overline{\sigma}(v)$ over all vertices $v$ of $G$. We give sharp upper bounds on the remoteness of simple triangulations and quadrangulations of given order and connectivity.https://dmtcs.episciences.org/6473/pdfmathematics - combinatorics |
| spellingShingle | Éva Czabarka Peter Dankelmann Trevor Olsen László A. Székely Wiener Index and Remoteness in Triangulations and Quadrangulations Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | Wiener Index and Remoteness in Triangulations and Quadrangulations |
| title_full | Wiener Index and Remoteness in Triangulations and Quadrangulations |
| title_fullStr | Wiener Index and Remoteness in Triangulations and Quadrangulations |
| title_full_unstemmed | Wiener Index and Remoteness in Triangulations and Quadrangulations |
| title_short | Wiener Index and Remoteness in Triangulations and Quadrangulations |
| title_sort | wiener index and remoteness in triangulations and quadrangulations |
| topic | mathematics - combinatorics |
| url | https://dmtcs.episciences.org/6473/pdf |
| work_keys_str_mv | AT evaczabarka wienerindexandremotenessintriangulationsandquadrangulations AT peterdankelmann wienerindexandremotenessintriangulationsandquadrangulations AT trevorolsen wienerindexandremotenessintriangulationsandquadrangulations AT laszloaszekely wienerindexandremotenessintriangulationsandquadrangulations |