Distance-uniform graphs with large diameter

DOI10.1137/17M115791XMaRDI QIDQ5232139zbMATH OpenOpenAlexWikidataFDO

Authors Mikhail Lavrov, Po-Shen Loh, Arnau Messegué

Publication date 29 August 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

diameterequilibriumextremal combinatoricsTower of Hanoinetwork creation

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Extremal problems in graph theory (05C35) Distance in graphs (05C12)

Abstract: An $epsilon$-distance-uniform graph is one in which from every vertex, all but an $epsilon$-fraction of the remaining vertices are at some fixed distance $d$, called the critical distance. We consider the maximum possible value of $d$ in an $epsilon$-distance-uniform graph with $n$ vertices. We show that for $frac1nleepsilonlefrac1logn$, there exist $epsilon$-distance-uniform graphs with critical distance $2^{Omega(fraclognlogepsilo{n}^{-1})}$, disproving a conjecture of Alon et al. that $d$ can be at most logarithmic in $n$. We also show that our construction is best possible, in the sense that an upper bound on $d$ of the form $2^{O(fraclognlogepsilo{n}^{-1})}$ holds for all $epsilon$ and $n$.

Recommendations

• The graph distance game
• Basic network creation games
• On tree equilibria in max-distance network creation games
• Diameter critical graphs
• scientific article; zbMATH DE number 1135688

Cites work

• A bounded budget network creation game
• Additive combinatorics
• Correction: ``Basic network creation games
• On a network creation game
• On nash equilibria for a network creation game
• On the tree conjecture for the network creation game
• Shortest paths between regular states of the Tower of Hanoi
• The Diameter of Random Graphs
• The max-distance network creation game on general host graphs
• The price of anarchy in network creation games
• The price of anarchy in network creation games is (mostly) constant

Cited in

(5)

• Uniform distances in rational unit-distance graphs
• A new family of distance-regular graphs with unbounded diameter
• On bipartite sum basic equilibria
• The diameter of sum basic equilibria games
• On the PoA Conjecture: Trees versus Biconnected Components

This page was built for publication: Distance-uniform graphs with large diameter

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