2021/12/16 by Vanessa Hiebeler, Hiebeler, Vanessa, Johannes Pardey +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2112.08805
Improving a recent result of Fundikwa, Mazorodze, and Mukwembi, we show that d ≤ (2n-3)/5 for every connected C4-free graph of order n, diameter d, and edge-connectivity at least 3, which is best possible up to a small additive constant. For edge-connectivity at least 4, we improve this to d ≤ (n-3)/3. Furthermore, adapting a construction due to Erdős, Pach, Pollack, and Tuza, for an odd prime power q at least 7, and every positive integer k, we show the existence of a connected C4-free graph of order n=(q2+q-1)k+1, diameter d=4k, and edge-connectivity λ at least q-6, in particular, d≥ 4(n-1)/(λ2+O(λ)).