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....
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2002 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2002
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/154677 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Bounds for graphs of given girth and generalized polygons / L. Benkherouf, V. Ustimenko // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 1–18. — Бібліогр.: 26 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862589225716678656 |
|---|---|
| author | Benkherouf, L. Ustimenko, V. |
| author_facet | Benkherouf, L. Ustimenko, V. |
| citation_txt | Bounds for graphs of given girth and generalized polygons / L. Benkherouf, V. Ustimenko // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 1–18. — Бібліогр.: 26 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| 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.
|
| first_indexed | 2025-11-27T02:29:08Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-154677 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-11-27T02:29:08Z |
| publishDate | 2002 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Benkherouf, L. Ustimenko, V. 2019-06-15T17:42:31Z 2019-06-15T17:42:31Z 2002 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 https://nasplib.isofts.kiev.ua/handle/123456789/154677 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. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Bounds for graphs of given girth and generalized polygons Article published earlier |
| spellingShingle | Bounds for graphs of given girth and generalized polygons Benkherouf, L. Ustimenko, V. |
| title | Bounds for graphs of given girth and generalized polygons |
| title_full | Bounds for graphs of given girth and generalized polygons |
| title_fullStr | Bounds for graphs of given girth and generalized polygons |
| title_full_unstemmed | Bounds for graphs of given girth and generalized polygons |
| title_short | Bounds for graphs of given girth and generalized polygons |
| title_sort | bounds for graphs of given girth and generalized polygons |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/154677 |
| work_keys_str_mv | AT benkheroufl boundsforgraphsofgivengirthandgeneralizedpolygons AT ustimenkov boundsforgraphsofgivengirthandgeneralizedpolygons |