Proximity in triangulations and quadrangulations

Eva Czabarka; Peter Dankelmann; Trevor Olsen; Laszlo A. Szekely

doi:10.5614/ejgta.2022.10.2.7

Proximity in triangulations and quadrangulations

Eva Czabarka, Peter Dankelmann, Trevor Olsen, Laszlo A. Szekely

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Let G be a connected graph. If (Formula Presented) denotes the arithmetic mean of the distances from v to all other vertices of G, then the proximity, (Formula Presented), of G is defined as the smallest value of (Formula Presented) over all vertices v of G. We give upper bounds for the proximity of simple triangulations and quadrangulations of given order and connectivity. We also construct simple triangulations and quadrangulations of given order and connectivity that match the upper bounds asymptotically and are likely optimal.

Original language	English
Pages (from-to)	425-446
Number of pages	22
Journal	Electronic Journal of Graph Theory and Applications
Volume	10
Issue number	2
DOIs	https://doi.org/10.5614/ejgta.2022.10.2.7
Publication status	Published - 2022

Keywords

Average distance
Connectivity
Distance
Maximal
Planar graph
Proximity
Quadrangulation
Triangulation
Upper bounds

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.5614/ejgta.2022.10.2.7

Cite this

@article{98c4d29f9d2944199db2f1b9c5fb8cd6,

title = "Proximity in triangulations and quadrangulations",

abstract = "Let G be a connected graph. If (Formula Presented) denotes the arithmetic mean of the distances from v to all other vertices of G, then the proximity, (Formula Presented), of G is defined as the smallest value of (Formula Presented) over all vertices v of G. We give upper bounds for the proximity of simple triangulations and quadrangulations of given order and connectivity. We also construct simple triangulations and quadrangulations of given order and connectivity that match the upper bounds asymptotically and are likely optimal.",

keywords = "Average distance, Connectivity, Distance, Maximal, Planar graph, Proximity, Quadrangulation, Triangulation, Upper bounds",

author = "Eva Czabarka and Peter Dankelmann and Trevor Olsen and Szekely, {Laszlo A.}",

year = "2022",

doi = "10.5614/ejgta.2022.10.2.7",

language = "English",

volume = "10",

pages = "425--446",

journal = "Electronic Journal of Graph Theory and Applications",

issn = "2338-2287",

publisher = "Indonesian Combinatorics Society",

number = "2",

}

TY - JOUR

T1 - Proximity in triangulations and quadrangulations

AU - Czabarka, Eva

AU - Dankelmann, Peter

AU - Olsen, Trevor

AU - Szekely, Laszlo A.

PY - 2022

Y1 - 2022

N2 - Let G be a connected graph. If (Formula Presented) denotes the arithmetic mean of the distances from v to all other vertices of G, then the proximity, (Formula Presented), of G is defined as the smallest value of (Formula Presented) over all vertices v of G. We give upper bounds for the proximity of simple triangulations and quadrangulations of given order and connectivity. We also construct simple triangulations and quadrangulations of given order and connectivity that match the upper bounds asymptotically and are likely optimal.

AB - Let G be a connected graph. If (Formula Presented) denotes the arithmetic mean of the distances from v to all other vertices of G, then the proximity, (Formula Presented), of G is defined as the smallest value of (Formula Presented) over all vertices v of G. We give upper bounds for the proximity of simple triangulations and quadrangulations of given order and connectivity. We also construct simple triangulations and quadrangulations of given order and connectivity that match the upper bounds asymptotically and are likely optimal.

KW - Average distance

KW - Connectivity

KW - Distance

KW - Maximal

KW - Planar graph

KW - Proximity

KW - Quadrangulation

KW - Triangulation

KW - Upper bounds

UR - http://www.scopus.com/inward/record.url?scp=85141789158&partnerID=8YFLogxK

U2 - 10.5614/ejgta.2022.10.2.7

DO - 10.5614/ejgta.2022.10.2.7

M3 - Article

AN - SCOPUS:85141789158

SN - 2338-2287

VL - 10

SP - 425

EP - 446

JO - Electronic Journal of Graph Theory and Applications

JF - Electronic Journal of Graph Theory and Applications

IS - 2

ER -

Proximity in triangulations and quadrangulations

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this