Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/809104
- Title
- On bipartite graphs of diameter 3 and defect 2
- Author/Creator
-
Delorme, Charles;
Jørgensen, Leif K.;
Miller, Mirka;
Pineda-Villavicencio, Guillermo
- Institution
- The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
- Description
- We consider bipartite graphs of degree ∆≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (∆, 3, −2) -graphs. We prove the uniqueness of the known bipartite (3, 3, −2) -graph and bipartite (4, 3, −2)-graph. We also prove several necessary conditions for the existence of bipartite (∆, 3, −2) -graphs. The most general of these conditions is that either ∆ or ∆−2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when ∆=6 and ∆=9, we prove the non-existence of the corresponding bipartite (∆, 3, −2)-graphs, thus establishing that there are no bipartite (∆, 3, −2)-graphs, for 5≤∆≤10.
- Relation
- Journal of Graph Theory Vol. 61, Issue 4, p. 271-288
- Publisher Link
- http://dx.doi.org/10.1002/jgt.20378
- Date
- 2009
- Publisher
- John Wiley & Sons
- Keyword(s)
-
degree problem for bipartite graphs;
diameter problem for bipartite graphs;
bipartite Moore bound;
bipartite Moore graphs;
defect
- Resource Type
- journal article
- Identifier
- http://hdl.handle.net/1959.13/809104
- Identifier
- ISSN:0364-9024
- Reviewed
17 Visitors
20 Hits
2 Downloads
