On graphs of maximum degree 3 and defect 4

Pineda-Villavicencio, Guillermo and Miller, Mirka 2008, On graphs of maximum degree 3 and defect 4, Journal of combinatorial mathematics and combinatorial computing, vol. 65, pp. 25-31.

Attached Files
Name Description MIMEType Size Downloads

Title On graphs of maximum degree 3 and defect 4
Author(s) Pineda-Villavicencio, GuillermoORCID iD for Pineda-Villavicencio, Guillermo orcid.org/0000-0002-2904-6657
Miller, Mirka
Journal name Journal of combinatorial mathematics and combinatorial computing
Volume number 65
Start page 25
End page 31
Total pages 7
Publisher Charles Babbage Research Centre
Place of publication Winnipeg, Man.
Publication date 2008-05
ISSN 0835-3026
Keyword(s) Degree/diameter problem
cubic graphs
Moore bound
Moore graphs
defect
Summary 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.
Language eng
Indigenous content off
Field of Research 0101 Pure Mathematics
0802 Computation Theory and Mathematics
0103 Numerical and Computational Mathematics
HERDC Research category C1.1 Refereed article in a scholarly journal
Copyright notice ©2008, Charles Babbage Research Centre
Persistent URL http://hdl.handle.net/10536/DRO/DU:30123271

Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 2 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 16 Abstract Views, 1 File Downloads  -  Detailed Statistics
Created: Tue, 25 Jun 2019, 12:16:30 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.