Concerning the Number of Edges in a Graph with Diameter Constraints

Abstract

We study problems related to the number of edges of a graph with diameter constraints. We show that the problem of finding, in a graph of diameter $k\ge 2$, a spanning subgraph of diameter $k$ with the minimum number of edges is NP-hard. In addition, we propose some efficient heuristic algorithms for solving this problem. We also investigate the number of edges in a critical graph of diameter 2. We collect some evidence which supports our conjecture that the number of edges in a critical graph of diameter 2 is at most $\mathrm{\Delta }(n-\mathrm{\Delta })$ where $\mathrm{\Delta }$ is the maximum degree. In particular, we show that our conjecture is true for $\mathrm{\Delta }\le \frac{1}{2}n$ or $\mathrm{\Delta }\ge n-5$.