Bounds for graphs of given girth and generalized polygons
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 bound...
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2002 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2002
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/154677 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Bounds for graphs of given girth and generalized polygons / L. Benkherouf, V. Ustimenko // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 1–18. — Бібліогр.: 26 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Резюме: | 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.
|
|---|---|
| ISSN: | 1726-3255 |