Premium
On bipartite graphs of diameter 3 and defect 2
Author(s) -
Delorme Charles,
Jørgensen Leif K.,
Miller Mirka,
PinedaVillavicencio Guillermo
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20378
Subject(s) - bipartite graph , combinatorics , mathematics , complete bipartite graph , discrete mathematics , edge transitive graph , cograph , foster graph , strong perfect graph theorem , triangle free graph , graph , 1 planar graph , chordal graph , line graph , voltage graph
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. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009