Deakin University
Browse

File(s) under permanent embargo

On graphs of maximum degree 3 and defect 4

journal contribution
posted on 2008-05-01, 00:00 authored by G Pineda-Villavicencio, M Miller
It is well known that apart from the Petersen graph there are no Moore graphs of degree 3. As a cubic graph must have an even number of vertices, there are no graphs of maximum degree 3 and δ vertices less than the Moore bound, where δ is odd. Additionally, it is known that there exist only three graphs of maximum degree 3 and 2 vertices less than the Moore bound. In this paper, we consider graphs of maximum degree 3, diameter D ≥ 2 and 4 vertices legs than the Moore bound, denoted as (3, D, 4)-graphs. We obtain all non-isomorphic (3, D, 4)-graphs for D = 2. Furthermore, for any diameter D, we consider the girth of (3, D, 4)-graphs. By a counting argument, it is easy to see that the girth is at least 2D - 2. The main contribution of this paper is that we prove that the girth of a (3, D, 4)-graph is at least 2D - 1. Finally, for D > 4, we conjecture that the girth of a (3, D, 4)-graph is 2D.

History

Journal

Journal of combinatorial mathematics and combinatorial computing

Volume

65

Pagination

25-31

Location

Winnipeg, Man.

ISSN

0835-3026

Language

eng

Publication classification

C1.1 Refereed article in a scholarly journal

Copyright notice

2008, Charles Babbage Research Centre

Publisher

Charles Babbage Research Centre