An asymptotic resolution of a problem of Plesník

DOI10.1016/J.JCTB.2020.06.003MaRDI QIDQ2200927zbMATH OpenOpenAlexFDO

Authors Stijn Cambie

Publication date 24 September 2020

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

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

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)

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.

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

Cites work

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

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)