Decreasing the diameter of triangle-free graphs: the open problem of Erdős, Gyárfás and Ruszinkó (1998) on the edge-addition parameter h_d(G)

For a triangle-free graph $G$, let $h_d(G)$ be the minimum number of edges that must be added to $G$, without adding vertices, so that the resulting graph is still triangle-free and has diameter at most $d$. Erdős, Gyárfás and Ruszinkó (Combinatorica 18, 1998) proved that $h_2(G)=\Theta(n\log n)$ for triangle-free graphs of order $n$ with no isolated vertices and fixed maximum degree, that the maximum of $h_2(G)$ over all triangle-free graphs of order $n$ equals $\lceil n/2-1\rceil\lfloor n/2-1\rfloor$ for all sufficiently large $n$ (attained by the double star), and that $h_3(G)\le n-1$ and $h_5(G)\le(n-1)/2$ for connected triangle-free graphs; by monotonicity this gives $h_4(G)\le n-1$. The paper's central question was left open and is re-posed as Problem 6 in Gyárfás's 2013 survey: does an absolute constant $\epsilon>0$ exist with $h_4(G)\le(1-\epsilon)n$ for every connected triangle-free graph $G$ on $n$ vertices? This question remains open.

Background

A graph is triangle-free if no three of its vertices are pairwise adjacent, and its diameter is the largest distance (shortest-path length) between two vertices. Erdős, Gyárfás and Ruszinkó (1998) asked how cheaply the diameter of a triangle-free graph can be reduced when the graph must remain triangle-free: for a triangle-free graph $G$, $h_d(G)$ is the minimum number of edges that must be added to $G$, without adding vertices, so that the resulting graph still contains no triangle and has diameter at most $d$. The constraint is what makes the problem nontrivial: an added edge may not join two vertices that have a common neighbor, since together with that common neighbor it would form a triangle. For $d=2$ the target condition — triangle-free with diameter at most 2 — is equivalent, for graphs with at least three vertices, to being a maximal triangle-free graph, meaning that no further edge can be added without creating a triangle; hence $h_2(G)$ is the minimum number of edges needed to complete $G$ into a maximal triangle-free graph.

The source paper mapped out the main regimes. Writing $n$ for the number of vertices and $D$ for the maximum degree, they proved $h_2(G)=\Theta(n\log n)$ for triangle-free graphs with no isolated vertices and fixed $D$. The proof works through inequalities relating $h_2(G)$ to edge clique cover parameters of the complement $\overline{G}$: an edge clique cover of a graph $H$ is a collection of complete subgraphs of $H$ whose edge sets together cover all edges of $H$, and it enters here because the neighborhoods created by a completion form cliques in $\overline{G}$. At the opposite extreme, the maximum of $h_2(G)$ over all triangle-free graphs of order $n$ is $\lceil n/2-1\rceil\,\lfloor n/2-1\rfloor$ for all sufficiently large $n$, attained by the double star — the tree consisting of a single central edge whose two endpoints are adjacent to $\lceil n/2-1\rceil$ and $\lfloor n/2-1\rfloor$ leaves; essentially all leaf-to-leaf edges across the central edge must be added. For larger target diameters they proved $h_3(G)\le n-1$ and $h_5(G)\le(n-1)/2$ for connected triangle-free $G$ (the first by an iterative center-plus-independent-set construction, the second by covering the vertices with stars centered at the endpoints of a maximum matching). Since $h_d(G)$ is nonincreasing in $d$, these give $h_4(G)\le n-1$, but no construction is known that saves a positive fraction of the edges when only diameter four is required.

The contrast with the unconstrained version shows what is missing. If the triangle-free condition on the augmented graph is dropped — define $f_d(G)$ as the minimum number of edges added to an arbitrary graph $G$ to reach diameter at most $d$ — then two of the authors, with Noga Alon, showed in 2000 that the problem is essentially solved: $f_2(G)=n-D-1$ exactly for fixed $D$ and large $n$, $f_3(G)\ge n-O(D^3)$, and the maximum of $f_d(G)$ over connected $n$-vertex graphs is $n/\lfloor d/2\rfloor-O(1)$ for every $d$. With the triangle-free constraint, the central worst-case question for $h_d$ remains the diameter-4 constant: whether $h_4(G)\le(1-\epsilon)n$ holds for every connected triangle-free graph $G$ of order $n$ with an absolute $\epsilon>0$.

Problem Statement

Let $G$ be a triangle-free graph on $n$ vertices and let $h_d(G)$ denote the minimum number of edges that must be added to $G$, without adding vertices, so that the resulting graph is still triangle-free and has diameter at most $d$. The scientific objective is the central question that Erdős, Gyárfás and Ruszinkó (1998) left open, re-posed as Problem 6 in Gyárfás's 2013 survey: does there exist an absolute constant $\epsilon>0$ such that $h_4(G)\le(1-\epsilon)\,n$ for every connected triangle-free graph $G$ on $n$ vertices? Since $h_3(G)\le n-1$ is known, the conjecture asks whether, once diameter four rather than three suffices, the worst-case number of added edges can always be reduced below $n$ by a fixed positive fraction; a negative answer would consist of connected triangle-free graphs with $h_4(G)/n\to 1$.

References

1. Paul Erdős, András Gyárfás, Miklós Ruszinkó, How to decrease the diameter of triangle-free graphs, Combinatorica 18, 493–501 (1998). DOI: 10.1007/s004930050035, https://doi.org/10.1007/s004930050035 (source paper).
2. András Gyárfás, Problems and memories, arXiv:1307.1768 [math.CO] (2013). https://arxiv.org/abs/1307.1768 (author survey; Section 3.1 restates the h_d results and re-poses the diameter-4 question as Problem 6).
3. Noga Alon, András Gyárfás, Miklós Ruszinkó, Decreasing the diameter of bounded degree graphs, Journal of Graph Theory 35(3), 161–172 (2000). DOI: 10.1002/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO;2-Y, https://doi.org/10.1002/1097-0118(200011)35:3%3C161::AID-JGT1%3E3.0.CO;2-Y (follow-up by two of the source authors; settles the unconstrained variant $f_d$ and cites the source paper only as related work; author's public preprint at https://www.math.tau.ac.il/~nogaa/PDFS/agr6.pdf).