- Title
- On large bipartite graphs of diameter 3
- Creator
- Feria-Puron, Ramiro; Miller, Mirka; Pineda-Villavicencio, Guillermo
- Relation
- ARC.DP110102011
- Relation
- Discrete Mathematics Vol. 313, Issue 4, p. 381-390
- Publisher Link
- http://dx.doi.org/10.1016/j.disc.2012.11.013
- Publisher
- Elsevier BV
- Resource Type
- journal article
- Date
- 2013
- Description
- We consider the bipartite version of the degree/diameter problem, namely, given natural numbers d≥2 and D≥2, find the maximum number Nᵇ(d, D) of vertices in a bipartite graph of maximum degree d and diameter D. In this context, the bipartite Moore bound Mᵇ(d,D) represents a general upper bound for Nᵇ(d,D). Bipartite graphs of order Mᵇ(d,D) are very rare, and determining Nb(d,D) still remains an open problem for most (d,D) pairs. This paper is a follow-up of our earlier paper (Feria-Purón and Pineda-Villavicencio, 2012 [5]), where a study on bipartite (d,D,−4)-graphs (that is, bipartite graphs of order Mb(d,D)−4) was carried out. Here we first present some structural properties of bipartite (d,3,−4)-graphs, and later prove that there are no bipartite (7,3,−4)-graphs. This result implies that the known bipartite (7,3,−6)-graph is optimal, and therefore Nᵇ(7,3)=80. We dub this graph the Hafner–Loz graph after its first discoverers Paul Hafner and Eyal Loz. The approach here presented also provides a proof of the uniqueness of the known bipartite (5,3,−4)-graph, and the non-existence of bipartite (6,3,−4)-graphs. In addition, we discover at least one new largest known bipartite–and also vertex-transitive–graph of degree 11, diameter 3 and order 190, a result which improves by four vertices the previous lower bound for Nᵇ(11,3).
- Subject
- degree/diameter problem for bipartite graphs; bipartite Moore bound; large bipartite graphs; defect
- Identifier
- http://hdl.handle.net/1959.13/1297308
- Identifier
- uon:19421
- Identifier
- ISSN:0012-365X
- Language
- eng
- Reviewed
- Hits: 1138
- Visitors: 1121
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|