Maximal cubic graphs with diameter 4 (Q1975363)

The construction of large interconnection or microprocessor networks gave rise to the \((\Delta,D)\)-graph problem: given two positive integers \(\Delta\) and \(D\), construct a connected \((\Delta,D)\)-graph (i.e. a graph of degree \(\Delta\) and diameter \(D\)) with a maximum number of vertices (a graph is of degree \(\Delta\) if all its vertices have degree \(\leq\Delta\), at least one of them being of degree \(\Delta\)). The author proves that there is no cubic graph with diameter \(4\) on \(40\) vertices. This implies that the maximal number of vertices of a \((3,4)\)-graph is \(38\).