- Title
- On graphs of defect at most 2
- Creator
- Feria-Purón, Ramiro; Miller, Mirka; Pineda-Villavicencio, Guillermo
- Date
- 2011
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/58296
- Identifier
- vital:4236
- Identifier
-
https://doi.org/10.1016/j.dam.2011.04.018
- Identifier
- ISSN:0166-218X
- Abstract
- In this paper we consider the degree/diameter problem, namely, given natural numbers Δ<2 and D<1, find the maximum number N(Δ,D) of vertices in a graph of maximum degree Δ and diameter D. In this context, the Moore bound M(Δ,D) represents an upper bound for N(Δ,D). Graphs of maximum degree Δ, diameter D and order M(Δ,D), called Moore graphs, have turned out to be very rare. Therefore, it is very interesting to investigate graphs of maximum degree Δ<2, diameter D<1 and order M(Δ,D)- with small >0, that is, (Δ,D,-)-graphs. The parameter is called the defect. Graphs of defect 1 exist only for Δ=2. When >1, (Δ,D,-)-graphs represent a wide unexplored area. This paper focuses on graphs of defect 2. Building on the approaches developed in Feria-Purón and Pineda-Villavicencio (2010) [11] we obtain several new important results on this family of graphs. First, we prove that the girth of a (Δ,D,-2)-graph with Δ<4 and D<4 is 2D. Second, and most important, we prove the non-existence of (Δ,D,-2)-graphs with even Δ<4 and D<4; this outcome, together with a proof on the non-existence of (4,3,-2)-graphs (also provided in the paper), allows us to complete the catalogue of (4,D,-)-graphs with D<2 and 0≤≤2. Such a catalogue is only the second census of (Δ,D,-2)-graphs known at present, the first being that of (3,D,-)-graphs with D<2 and 0≤≤2 Jørgensen (1992) [14]. Other results of this paper include necessary conditions for the existence of (Δ,D,-2)-graphs with odd Δ<5 and D<4, and the non-existence of (Δ,D,-2)-graphs with odd Δ<5 and D<5 such that Δ≡0,2(modD). Finally, we conjecture that there are no (Δ,D,-2)-graphs with Δ<4 and D<4, and comment on some implications of our results for the upper bounds of N(Δ,D). © 2011 Elsevier B.V. All rights reserved.
- Relation
- Discrete Applied Mathematics Vol. 159, no. 13 (2011), p. 1331-1344
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- Defect; Degree/diameter problem; Moore bound; Moore graph; Repeat; Maximum degree; Natural number; Upper bound; Graphic methods
- Full Text
- Reviewed
- Hits: 1500
- Visitors: 1607
- Downloads: 153
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE2 | Accepted version | 240 KB | Adobe Acrobat PDF | View Details Download |