On bipartite graphs of defect at most 4

Details On bipartite graphs of defect at most 4 On bipartite graphs of defect at most 4

2010-10-27

arxiv.org/abs/1010.5651v2

Discrete Applied Mathematics 160 (2012), 140-154

Mathematics

Combinatorics

25 pages, 14 Postscript figures

Scientific paper

10.1016/j.dam.2011.09.002

We consider the bipartite version of the degree/diameter problem, namely, given natural numbers {\Delta} \geq 2 and D \geq 2, find the maximum number Nb({\Delta},D) of vertices in a bipartite graph of maximum degree {\Delta} and diameter D. In this context, the Moore bipartite bound Mb({\Delta},D) represents an upper bound for Nb({\Delta},D). Bipartite graphs of maximum degree {\Delta}, diameter D and order Mb({\Delta},D), called Moore bipartite graphs, have turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree {\Delta} \geq 2, diameter D \geq 2 and order Mb({\Delta},D) - \epsilon with small \epsilon > 0, that is, bipartite ({\Delta},D,-\epsilon)-graphs. The parameter \epsilon is called the defect. This paper considers bipartite graphs of defect at most 4, and presents all the known such graphs. Bipartite graphs of defect 2 have been studied in the past; if {\Delta} \geq 3 and D \geq 3, they may only exist for D = 3. However, when \epsilon > 2 bipartite ({\Delta},D,-\epsilon)-graphs represent a wide unexplored area. The main results of the paper include several necessary conditions for the existence of bipartite $(\Delta,d,-4)$-graphs; the complete catalogue of bipartite (3,D,-\epsilon)-graphs with D \geq 2 and 0 \leq \epsilon \leq 4; the complete catalogue of bipartite ({\Delta},D,-\epsilon)-graphs with {\Delta} \geq 2, 5 \leq D \leq 187 (D /= 6) and 0 \leq \epsilon \leq 4; and a non-existence proof of all bipartite ({\Delta},D,-4)-graphs with {\Delta} \geq 3 and odd D \geq 7. Finally, we conjecture that there are no bipartite graphs of defect 4 for {\Delta} \geq 3 and D \geq 5, and comment on some implications of our results for upper bounds of Nb({\Delta},D).

Affiliated with

Also associated with

No associations

Rating

On bipartite graphs of defect at most 4 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 bipartite graphs of defect at most 4, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On bipartite graphs of defect at most 4 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-485504