Maximal cubic graphs with diameter 4
type: Item
instance of: scholarly article
title: Maximal cubic graphs with diameter 4
zbMATH Open document ID: 0949.05043
DOI: 10.1016/S0166-218X(99)00204-8
author: Dominique Buset
published in: Discrete Applied Mathematics
publication date: 2000-06-22T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1428616
zbMATH Keywords: cubic graph
zbMATH Keywords: diameter
reviewed by: Chunhui Lai
MaRDI profile type: Publication
cites work: Q5183530
cites work: Regular graphs with excess one
cites work: Q4739935
cites work: Large graphs with given degree and diameter. II
cites work: Large Graphs with Given Degree and Diameter III
cites work: Table of large \(({\Delta{}}, D)\)-graphs
cites work: Q4770409
cites work: Q5677530
cites work: On Moore Graphs with Diameters 2 and 3
cites work: Diameters of cubic graphs
cites work: Nonexistence of certain cubic graphs with small diameters
full work available at URL: s0166-218x(99)00204-8
OpenAlex ID: W2069815963
description: scientific article; zbMATH DE number 1428616