Maximal cubic graphs with diameter 4 (Q1975363)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximal cubic graphs with diameter 4 |
scientific article |
Statements
Maximal cubic graphs with diameter 4 (English)
0 references
22 June 2000
0 references
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\).
0 references
cubic graph
0 references
diameter
0 references