History

Please fill in your query. A complete syntax description you will find on the General Help page.
On large $(Δ, D, D, 1)$-graphs. (English)
Networks 57, No. 4, 316-327 (2011).
Summary: Concern about fault tolerance in the design of interconnection networks has aroused interest in finding large graphs such that the subgraphs obtained by deleting any set of up to $s$ vertices have small diameter. Clearly, $1 \le s \le Δ- 1$, where $Δ$ is the maximum degree of the graph. Graphs of maximum degree $Δ$, diameter $\le D$ and such that the graphs obtained by deletion of up to $s$ vertices have diameter $\le D^{\prime}$ are known as ($Δ, D, D^{\prime}, s)$-graphs. This article considers the case $s = 1$ and $D = D^{\prime}$. In other words, it deals with the search for large graphs whose diameter does not increase after deleting one vertex. The article also contains an updated table of the largest known $(Δ, D, D, 1)$-graphs, in which most of the entries correspond to the constructions put forward in this article.