|
|||||
|
|
Complete catalogue of graphs of maximum degree 3 and defect at most 4 |
|
| Authors: | Mirka Miller Guillermo Pineda-Villavicencio |
| Institution: | a School of Electrical Engineering and Computer Science, The University of Newcastle, Callaghan, NSW 2308, Australia b Department of Mathematics, University of West Bohemia, Univerzitni 8, 306 14 Pilsen, Czech Republic c Graduate School of Information Technology and Mathematical Sciences, University of Ballarat, Ballarat, Victoria 3353, Australia |
| Abstract: | 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,−?)-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 N3,D of vertices in a graph of maximum degree 3 and diameter D, so that N3,D≤M3,D−6 for D≥5. |
| Keywords: | Degree/diameter problem Cubic graphs Moore bound Moore graphs Defect |
| 本文献已被 ScienceDirect 等数据库收录！ | |