- Title
- On graphs of defect at most 2
- Creator
- Feria-Purón, Ramiro; Miller, Mirka; Pineda-Villavicencio, Guillermo
- Relation
- Discrete Applied Mathematics Vol. 159, Issue 13, p. 1331-1344
- Publisher Link
- http://dx.doi.org/10.1016/j.dam.2011.04.018
- Publisher
- Elsevier BV
- Resource Type
- journal article
- Date
- 2011
- Description
- 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, 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 [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 the one of (3,D,−ε)-graphs with D ≥ 2 and 0 ≤ ε ≤ 2 [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 (mod D). 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).
- Subject
- Moore bound; Moore graphs; degree/diameter problem; defects; repeat
- Identifier
- http://hdl.handle.net/1959.13/920703
- Identifier
- uon:9198
- Identifier
- ISSN:0166-218X
- Language
- eng
- Full Text
- Reviewed
- Hits: 1234
- Visitors: 1548
- Downloads: 152
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 239 KB | Adobe Acrobat PDF | View Details Download |