Bounds for graphs of given girth and generalized polygons
In this paper we present a bound for bipartite graphs with average bidegrees \(\eta \) and \(\xi \) satisfying the inequality \(\eta \geq {\xi }^{\alpha }\), \( \alpha \geq 1\). This bound turns out to be the sharpest existing bound. Sizes of known families of finite generalized polygons are exactly...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Lugansk National Taras Shevchenko University
2018
|
| Теми: | |
| Онлайн доступ: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Репозитарії
Algebra and Discrete Mathematics| id |
oai:ojs.admjournal.luguniv.edu.ua:article-1 |
|---|---|
| record_format |
ojs |
| spelling |
oai:ojs.admjournal.luguniv.edu.ua:article-12018-05-16T09:50:29Z Bounds for graphs of given girth and generalized polygons Benkherouf, Lakdere Ustimenko, Vasyl Extremal Graph Theory, Operations Research, Family 90B06, 05C80, 05D409, 05D99 In this paper we present a bound for bipartite graphs with average bidegrees \(\eta \) and \(\xi \) satisfying the inequality \(\eta \geq {\xi }^{\alpha }\), \( \alpha \geq 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\geq 2t+1\). This bound has the same magnitude as that of Erdos bound, which estimates the size of graphs without cycles \(C_{2t}\). Lugansk National Taras Shevchenko University 2018-05-15 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1 Algebra and Discrete Mathematics; Vol 1, No 1 (2002) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1/123 Copyright (c) 2015 Algebra and Discrete Mathematics |
| institution |
Algebra and Discrete Mathematics |
| collection |
OJS |
| language |
English |
| topic |
Extremal Graph Theory Operations Research Family 90B06 05C80 05D409 05D99 |
| spellingShingle |
Extremal Graph Theory Operations Research Family 90B06 05C80 05D409 05D99 Benkherouf, Lakdere Ustimenko, Vasyl Bounds for graphs of given girth and generalized polygons |
| topic_facet |
Extremal Graph Theory Operations Research Family 90B06 05C80 05D409 05D99 |
| format |
Article |
| author |
Benkherouf, Lakdere Ustimenko, Vasyl |
| author_facet |
Benkherouf, Lakdere Ustimenko, Vasyl |
| author_sort |
Benkherouf, Lakdere |
| title |
Bounds for graphs of given girth and generalized polygons |
| title_short |
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_sort |
bounds for graphs of given girth and generalized polygons |
| description |
In this paper we present a bound for bipartite graphs with average bidegrees \(\eta \) and \(\xi \) satisfying the inequality \(\eta \geq {\xi }^{\alpha }\), \( \alpha \geq 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\geq 2t+1\). This bound has the same magnitude as that of Erdos bound, which estimates the size of graphs without cycles \(C_{2t}\). |
| publisher |
Lugansk National Taras Shevchenko University |
| publishDate |
2018 |
| url |
https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1 |
| work_keys_str_mv |
AT benkherouflakdere boundsforgraphsofgivengirthandgeneralizedpolygons AT ustimenkovasyl boundsforgraphsofgivengirthandgeneralizedpolygons |
| first_indexed |
2024-04-12T06:26:41Z |
| last_indexed |
2024-04-12T06:26:41Z |
| _version_ |
1796109187651993600 |