On graphs of defect at most 2
- Authors: Feria-Purón, Ramiro , Miller, Mirka , Pineda-Villavicencio, Guillermo
- Date: 2011
- Type: Text , Journal article
- Relation: Discrete Applied Mathematics Vol. 159, no. 13 (2011), p. 1331-1344
- Full Text:
- Reviewed:
- 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, 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.
Complete catalogue of graphs of maximum degree 3 and defect at most 4
- Authors: Miller, Mirka , Pineda-Villavicencio, Guillermo
- Date: 2009
- Type: Text , Journal article
- Relation: Discrete Applied Mathematics Vol. 157, no. 13 (2009), p. 2983-2996
- Full Text:
- Reviewed:
- Description: We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M3,D, that is, (3,D,−)-graphs for ≤4. We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−)-graphs with D≥2 and ≤4. Our results also give an improvement to the upper bound on the largest possible number N3,D of vertices in a graph of maximum degree 3 and diameter D, so that N3,D≤M3,D−6 for D≥5. Copyright Elsevier.
New largest known graphs of diameter 6
- Authors: Pineda-Villavicencio, Guillermo , Gómez, José , Miller, Mirka , Pérez-Rosés, Hebert
- Date: 2009
- Type: Text , Journal article
- Relation: Networks Vol. 53, no. 4 (2009), p. 315-328
- Full Text:
- Reviewed:
- Description: In the pursuit of obtaining largest graphs of given maximum degree
- Description: 2003007890
New largest graphs of diameter 6. (Extended Abstract)
- Authors: Pineda-Villavicencio, Guillermo , Gomez, Jose , Miller, Mirka , Pérez-Rosés, Hebert
- Date: 2006
- Type: Text , Journal article
- Relation: Electronic Notes in Discrete Mathematics Vol. 24, no. (2006), p. 153-160
- Full Text:
- Reviewed:
- Description: In the pursuit of obtaining largest graphs of given degree and diameter, many construction techniques have arisen. Compounding of graphs is one such technique. In this paper, by means of the compounding of complete graphs into the bipartite Moore graph of diameter 6, we obtain two families of (
- Description: C1