On bipartite graphs of diameter 3 and defect 2

Title: On bipartite graphs of diameter 3 and defect 2
Creator: Delorme, Charles; Jørgensen, Leif K.; Miller, Mirka; Pineda-Villavicencio, Guillermo
Relation: Journal of Graph Theory Vol. 61, Issue 4, p. 271-288
Publisher Link: http://dx.doi.org/10.1002/jgt.20378
Publisher: John Wiley & Sons
Resource Type: journal article
Date: 2009
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.
Subject: degree problem for bipartite graphs; diameter problem for bipartite graphs; bipartite Moore bound; bipartite Moore graphs; defect
Identifier: http://hdl.handle.net/1959.13/809104
Identifier: uon:7820
Identifier: ISSN:0364-9024
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format