Premium
Bipartite regular graphs with fixed diameter
Author(s) -
Broersma H. J.,
Göbel F.
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230260303
Subject(s) - combinatorics , bipartite graph , mathematics , graph , upper and lower bounds , prime (order theory) , discrete mathematics , mathematical analysis
For given nonnegative integers k and D , we consider the problem of determining n 0 (k, D), The smallest number n for which there exists a k ‐regular bipartite graph on n vertices with diameter D . We solve the problem for all pairs (k, D ) with D ≢ 2 (mod 4) and D ≢ 3 (mod 4), for all pairs ( k , D ) with k even or k prime and D ≢ 3 (mod 4), for all pairs with D ≤ 9 or k ≤ 4, and for a few other pairs. in the remaining cases, we obtain lower and upper bounds for n 0 (k, D).