Complete catalogue of graphs of maximum degree 3 and defect at most 4

Title: Complete catalogue of graphs of maximum degree 3 and defect at most 4
Creator: Miller, Mirka; Pineda-Villavicencio, Guillermo
Relation: Discrete Applied Mathematics Vol. 157, Issue 13, p. 2983-2996
Publisher Link: http://dx.doi.org/10.1016/j.dam.2009.04.021
Publisher: Elsevier
Resource Type: journal article
Date: 2009
Description: We consider graphs of maximum degree 3, diameter D ≥ 2 and at most 4 vertices less than the Moore bound M₃,ᴅ, that is, (3,D,−ϵ)-graphs for ϵ ≤ 4. We prove the non-existence of (3,D,−4)-graphs for D ≥ 5, completing in this way the catalogue of (3,D,−ϵ)-graphs with D ≥ 2 and ϵ ≤ 4. Our results also give an improvement to the upper bound on the largest possible number N₃,ᴅ of vertices in a graph of maximum degree 3 and diameter D, so that N₃,ᴅ ≤ M₃,ᴅ − 6 for D ≥ 5.
Subject: degree problem; diameter problem; cubic graphs; Moore bound; Moore graphs; defect
Identifier: http://hdl.handle.net/1959.13/809115
Identifier: uon:7828
Identifier: ISSN:0166-218X
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format