Maximal cubic graphs with diameter 4
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\).
- Diameters of cubic graphs
- scientific article; zbMATH DE number 3794103 (Why is no real title available?)
- scientific article; zbMATH DE number 3445271 (Why is no real title available?)
- scientific article; zbMATH DE number 3432305 (Why is no real title available?)
- scientific article; zbMATH DE number 3412694 (Why is no real title available?)
- Large Graphs with Given Degree and Diameter III
- Large graphs with given degree and diameter. II
- Nonexistence of certain cubic graphs with small diameters
- On Moore Graphs with Diameters 2 and 3
- Regular graphs with excess one
- Table of large \(({\Delta{}}, D)\)-graphs
- Vertex-symmetric generalized Moore graphs.
- An explicit infinite family of \(\mathbb{M}\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)]\log_{K-1}\mathbb{M}\) for each \(K-1\) a prime power
- On graphs of defect at most 2
- New largest known graphs of diameter 6
- On graphs of maximum degree 3 and defect 4
- Nonexistence of certain cubic graphs with small diameters
- Complete catalogue of graphs of maximum degree 3 and defect at most 4
This page was built for publication: Maximal cubic graphs with diameter 4
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1975363)
