An asymptotic resolution of a problem of Plesník

DOI10.1016/J.JCTB.2020.06.003zbMATH Open1448.05085arXiv1811.08334OpenAlexW3036892734MaRDI QIDQ2200927FDOQ2200927

Authors: Stijn Cambie 

Publication date: 24 September 2020

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Fix $dge3$. We show the existence of a constant $c>0$ such that any graph of diameter at most $d$ has average distance at most $d-cfrac{d}^{3/2}sqrtn$, where $n$ is the number of vertices. Moreover, we exhibit graphs certifying sharpness of this bound up to the choice of $c$. This constitutes an asymptotic solution to a longstanding open problem of Plesn'{i}k. Furthermore we solve the problem exactly for digraphs if the order is large compared with the diameter.

Full work available at URL: https://arxiv.org/abs/1811.08334

Recommendations

• An asymptotic resolution of a conjecture of Szemerédi and Petruska
• On the number of solutions to the asymptotic plateau problem
• The asymptotic soluction of the kiefer–weiss problem
• Asymptotic for a Riemann-Hilbert problem solution
• On a problem of A. Pleijel
• scientific article; zbMATH DE number 4188448
• Asymptotics of solutions of a cauchy problem
• On asymptotics of solutions of poincare difference systems
• scientific article; zbMATH DE number 1028874
• scientific article; zbMATH DE number 23193

zbMATH Keywords

digraphsdiameterextremal problemsWiener indexaverage distance

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Extremal problems in graph theory (05C35) Distance in graphs (05C12)

Cites Work

• The Average Distance in a Random Graph with Given Expected Degrees
• On the sum of all distances in a graph or digraph
• Wiener index of trees of given order and diameter at most 6
• Diameters in graphs
• Spanning trees with many leaves and average distance

Cited In (11)

• Average distance, radius and remoteness of a graph
• Selected topics on Wiener index
• Kemeny's constant and Wiener index on trees
• Extremal total distance of graphs of given radius I
• A conjecture on average distance and diameter of a graph
• Bounding the \(k\)-Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence
• Diameter and inverse degree
• The extremal average distance of cubic graphs
• Average Distance and Edge-Connectivity I
• Proof of a conjecture on Wiener index and eccentricity of a graph due to edge contraction
• Maximum size of digraphs of given radius

This page was built for publication: An asymptotic resolution of a problem of Plesník

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200927)