Premium
Large bipartite graphs with given degree and diameter
Author(s) -
Delorme C.
Publication year - 1985
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.3190090304
Subject(s) - combinatorics , bipartite graph , mathematics , degree (music) , complete bipartite graph , discrete mathematics , pancyclic graph , chordal graph , graph , 1 planar graph , physics , acoustics
We give constructions of bipartite graphs with maximum Δ, diameter D on B vertices, such that for every D ≥ 2 the lim inf Δ→∞ B . Δ 1‐D = b D > 0. We also improve similar results on ordinary graphs, for example, we prove that lim Δ→∞ N · Δ −D = 1 if D is 3 or 5. This is a partial answer to a problem of Bollobás.