Bounds for graphs of given girth and generalized polygons
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Bounds for graphs of given girth and generalized polygons
|
|
| Creator |
Benkherouf, L.
Ustimenko, V. |
|
| Description |
In this paper we present a bound for bipartite graphs with average bidegrees η and ξ satisfying the inequality η ≥ ξ α, α ≥ 1. This bound turns out to be the sharpest existing bound. Sizes of known families of finite generalized polygons are exactly on that bound. Finally, we present lower bounds for the numbers of points and lines of biregular graphs (tactical configurations) in terms of their bidegrees. We prove that finite generalized polygons have smallest possible order among tactical configuration of given bidegrees and girth. We also present an upper bound on the size of graphs of girth g ≥ 2t + 1. This bound has the same magnitude as that of Erd¨os bound, which estimates the size of graphs without cycles C₂t. |
|
| Date |
2019-06-15T17:42:31Z
2019-06-15T17:42:31Z 2002 |
|
| Type |
Article
|
|
| Identifier |
Bounds for graphs of given girth and generalized polygons / L. Benkherouf, V. Ustimenko // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 1–18. — Бібліогр.: 26 назв. — англ.
1726-3255 2001 Mathematics Subject Classification 90B06, 05C80, 05D409, 05D99, 05E20 http://dspace.nbuv.gov.ua/handle/123456789/154677 |
|
| Language |
en
|
|
| Relation |
Algebra and Discrete Mathematics
|
|
| Publisher |
Інститут прикладної математики і механіки НАН України
|
|