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...

Full description

Saved in:
Bibliographic Details
Date:2018
Main Authors: Benkherouf, Lakdere, Ustimenko, Vasyl
Format: Article
Language:English
Published: Lugansk National Taras Shevchenko University 2018
Subjects:
Online Access:https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Algebra and Discrete Mathematics

Institution

Algebra and Discrete Mathematics
Description
Summary: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}\).