- Title
- On bipartite graphs of defect at most 4
- Creator
- Feria-Purón, Ramiro; Pineda-Villavicencio, Guillermo
- Date
- 2011
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/43184
- Identifier
- vital:4267
- Identifier
-
https://doi.org/10.1016/j.dam.2011.09.002
- Identifier
- ISSN:0166-218X
- Abstract
- We consider the bipartite version of the degree/diameter problem, namely, given natural numbers Δ ≥ 2 and D ≥ 2, find the maximum number Nb (Δ, D) of vertices in a bipartite graph of maximum degree Δ and diameter D. In this context, the Moore bipartite bound Mb (Δ, D) represents an upper bound for Nb (Δ, D). Bipartite graphs of maximum degree Δ, diameter D and order Mb (Δ, D)-called Moore bipartite graphs-have turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree Δ ≥ 2, diameter D ≥ 2 and order Mb (Δ, D) - ε{lunate} with small ε{lunate} > 0, that is, bipartite (Δ, D, - ε{lunate})-graphs. The parameter ε{lunate} 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 Δ ≥ 3 and D ≥ 3, they may only exist for D = 3. However, when ε{lunate} > 2 bipartite (Δ, D, - ε{lunate})-graphs represent a wide unexplored area. The main results of the paper include several necessary conditions for the existence of bipartite (Δ, D, - 4)-graphs; the complete catalogue of bipartite (3, D, - ε{lunate})-graphs with D ≥ 2 and 0 ≤ ε{lunate} ≤ 4; the complete catalogue of bipartite (Δ, D, - ε{lunate})-graphs with Δ ≥ 2, 5 ≤ D ≤ 187 (D ≠6) and 0 ≤ ε{lunate} ≤ 4; a proof of the non-existence of all bipartite (Δ, D, - 4)-graphs with Δ ≥ 3 and odd D ≥ 5. Finally, we conjecture that there are no bipartite graphs of defect 4 for Δ ≥ 3 and D ≥ 5, and comment on some implications of our results for the upper bounds of Nb (Δ, D). © 2011 Elsevier B.V. All rights reserved.
- Relation
- Discrete Applied Mathematics Vol.160, no.1-2 (2011), p.140-154
- Rights
- Copyright Elsevier B.V.
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- Defect; Degree/diameter problem for bipartite graphs; Moore bipartite bound; Moore bipartite graph; Repeat
- Full Text
- Reviewed
- Hits: 814
- Visitors: 961
- Downloads: 166
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Accepted version | 257 KB | Adobe Acrobat PDF | View Details Download |