- Title
- On bipartite graphs of defect at most 4
- Creator
- Feria-Purón, Ramiro; Pineda-Villavicencio, Guillermo
- Relation
- Discrete Applied Mathematics Vol. 160, Issue 1-2, p. 140-154
- Publisher Link
- http://dx.doi.org/10.1016/j.dam.2011.09.002
- Publisher
- Elsevier BV, North-Holland
- Resource Type
- journal article
- Date
- 2012
- Description
- We consider the bipartite version of the degree/diameter problem, namely, given natural numbers Δ≥2 and D≥2, find the maximum number [formula could not be replicated] of vertices in a bipartite graph of maximum degree Δ and diameter D. In this context, the Moore bipartite bound [formula could not be replicated] represents an upper bound for [formula could not be replicated]. Bipartite graphs of maximum degree Δ, diameter D and order [formula could not be replicated] –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 [formula could not be replicated] with small ϵ>0, that is, bipartite (Δ,D,−ϵ)-graphs. The parameter ϵ 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 ϵ>2 bipartite (Δ,D,−ϵ)-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,−ϵ)-graphs with D≥2 and 0≤ϵ≤4; the complete catalogue of bipartite (Δ,D,−ϵ)-graphs with Δ≥2, 5≤D≤187 (D≠6) and 0≤ϵ≤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 [formula could not be replicated].
- Subject
- Moore bipartite bound; Moore bipartite graph; degree/diameter problem for bipartite graphs; defect; repeat
- Identifier
- http://hdl.handle.net/1959.13/1310763
- Identifier
- uon:22080
- Identifier
- ISSN:0166-218X
- Language
- eng
- Reviewed
- Hits: 1095
- Visitors: 1030
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|