Deakin University
Browse
1/1
2 files

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

journal contribution
posted on 2009-07-01, 00:00 authored by M Miller, G Pineda-Villavicencio
We consider graphs of maximum degree 3, diameter D ≥ 2 and at most 4 vertices less than the Moore bound M3, D, that is, (3, D, - ε{lunate})-graphs for ε{lunate} ≤ 4. We prove the non-existence of (3, D, - 4)-graphs for D ≥ 5, completing in this way the catalogue of (3, D, - ε{lunate})-graphs with D ≥ 2 and ε{lunate} ≤ 4. Our results also give an improvement to the upper bound on the largest possible number N3, D of vertices in a graph of maximum degree 3 and diameter D, so that N3, D ≤ M3, D - 6 for D ≥ 5.

History

Journal

Discrete applied mathematics

Volume

157

Issue

13

Pagination

2983 - 2996

Publisher

Elsevier

Location

Amsterdam, The Netherlands

ISSN

0166-218X

Language

eng

Publication classification

C1.1 Refereed article in a scholarly journal

Copyright notice

2009, Elsevier B.V.