On bipartite graphs of diameter 3 and defect 2 | Zendy

Delorme Charles | Zendy; Jørgensen Leif K. | Zendy; Miller Mirka | Zendy; PinedaVillavicencio Guillermo | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research