On graphs of defect at most 2

Ramiro Feria-Puron, Mirka Miller, Guillermo Pineda-Villavicencio

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

In this paper we consider the degree/diameter problem, namely, given natural numbers Delta > 2 and D >= 1, find the maximum number N(Delta, D) of vertices in a graph of maximum degree Delta and diameter D. In this context, the Moore bound M(Delta, D) represents an upper bound for N(Delta, D). Graphs of maximum degree Delta, diameter D and order M(Delta, D), called Moore graphs, have turned out to be very rare. Therefore, it is very interesting to investigate graphs of maximum degree Delta >= 2, diameter D >= 1 and order M(Delta, D) - epsilon with small epsilon > 0, that is, (Delta, D, -epsilon)-graphs. The parameter epsilon is called the defect. Graphs of defect 1 exist only for Delta = 2. When epsilon > 1, (Delta, D, -epsilon)-graphs represent a wide unexplored area. This paper focuses on graphs of defect 2. Building on the approaches developed in Feria-Puron and Pineda-Villavicencio (2010) [11] we obtain several new important results on this family of graphs. First, we prove that the girth of a (Delta, D, -2)-graph with Delta >= 4 and D >= 4 is 2D. Second, and most important, we prove the non-existence of (Delta, D, -2)-graphs with even Delta >= 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, -epsilon)-graphs with D >= 2 and 0 = 2 and 0 = 5 and D >= 4, and the non-existence of (Delta, D, -2)-graphs with odd Delta >= 5 and D >= 5 such that Delta equivalent to 0, 2 (mod D). Finally, we conjecture that there are no (Delta, D, -2)-graphs with Delta >= 4 and D >= 4, and comment on some implications of our results for the upper bounds of N(Delta, D). (C) 2011 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)1331 - 1344
Number of pages14
JournalDISCRETE APPLIED MATHEMATICS
Volume159
Issue number13
DOIs
Publication statusPublished - 6 Aug 2011

Fingerprint

Dive into the research topics of 'On graphs of defect at most 2'. Together they form a unique fingerprint.

Cite this