On graphs of defect at most 2

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

22 pages, 11 Postscript figures

Scientific paper

10.1016/j.dam.2011.04.018

In this paper we consider the degree/diameter problem, namely, given natural numbers {\Delta} \geq 2 and D \geq 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, turned out to be very rare. Therefore, it is very interesting to investigate graphs of maximum degree {\Delta} \geq 2, diameter D \geq 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 [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} \geq 4 and D \geq 4 is 2D. Second, and most important, we prove the non-existence of ({\Delta},D,-2)-graphs with even {\Delta} \geq 4 and D \geq 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 \geq 2 and 0 \leq {\epsilon} \leq 2. Such a catalogue is only the second census of ({\Delta},D,-2)-graphs known at present, the first being the one of (3,D,-{\epsilon})-graphs with D \geq 2 and 0 \leq {\epsilon} \leq 2 [14]. Other results of this paper include necessary conditions for the existence of ({\Delta},D,-2)-graphs with odd {\Delta} \geq 5 and D \geq 4, and the non-existence of ({\Delta},D,-2)-graphs with odd {\Delta} \geq 5 and D \geq 5 such that {\Delta} \equiv 0, 2 (mod D).

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On graphs of defect at most 2 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On graphs of defect at most 2, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On graphs of defect at most 2 will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-485540

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.