- Title
- On large bipartite graphs of diameter 3
- Creator
- Feria-Purón, Ramiro; Miller, Mirka; Pineda-Villavicencio, Guillermo
- Date
- 2013
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/44102
- Identifier
- vital:4958
- Identifier
-
https://doi.org/10.1016/j.disc.2012.11.013
- Identifier
- ISSN:0012-365x
- Abstract
- We consider the bipartite version of the degree/diameter problem, namely, given natural numbers d≥2 and D≥2, find the maximum number N b(d,D) of vertices in a bipartite graph of maximum degree d and diameter D. In this context, the bipartite Moore bound Mb(d,D) represents a general upper bound for Nb(d,D). Bipartite graphs of order Mb(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 M b(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 Nb(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 Nb(11,3). © 2012 Elsevier B.V. All rights reserved.
- Relation
- Discrete Mathematics Vol. 313, no. 4 (2013), p. 381-390; http://purl.org/au-research/grants/arc/DP110102011
- Rights
- Copyright 2012 Elsevier B.V
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0101 Pure Mathematics; 0102 Applied Mathematics; Bipartite Moore bound; Defect; Degree/diameter problem for bipartite graphs; Large bipartite graphs
- Full Text
- Reviewed
- Hits: 1571
- Visitors: 2243
- Downloads: 141
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE2 | Accepted Version | 188 KB | Adobe Acrobat PDF | View Details Download |