Size of graphs and digraphs with given diameter and connectivity constraints
For a connected, finite graph or a strongly connected finite digraph, the diameter is the largest of all distances between pairs of vertices; the edge-connectivity is the minimum number of edges (respectively arcs) whose removal renders a graph \(G\) (respectively a strong digraph \(G\)) disconnected (respectively not strongly connected); a strongly connected digraph is Eulerian if, for every vertex, the in-degree and out-degree coincide. In the first instance this paper addresses gaps in the literature relating, for undirected \(G=(V,E)\), \(\vert V\vert \), \(\vert E\vert \), diameter, and edge-connectivity. It also seeks, in \S4, to generalize results to Eulerian digraphs, relating e.g. \textit{P. Dankelmann} and \textit{L. Volkmann} [Electron. J. Comb. 17, No. 1, Research Paper R157, 11 p. (2010; Zbl 1204.05042)]. In Theorem 1 the author determines for graphs \(G=(V,E)\) the maximum of \(\vert E\vert \) given \(\vert V\vert \), diameter, and edge-connectity \(\lambda\), where \(2\le\lambda\le 7\); for \(\lambda=1\) this is a classical result.
scientific article; zbMATH DE number 7377535