|
Algebra and Discrete Mathematics, 2002, Issue 1, Pages 1–18
(Mi adm298)
|
|
|
|
RESEARCH ARTICLE
Bounds for graphs of given girth and generalized polygons
Lakdere Benkherouf, Vasyl Ustimenko Department of Mathematics and Statistics, Sultan Qaboos University, P.O.Box 36, Al-Khod 123, Oman
Abstract:
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 Erdös bound, which estimates the size of graphs without cycles $C_{2t}$.
Keywords:
Extremal Graph Theory, Operations Research, Family of Graphs of High Girth, Simple Groups of Lie Type.
Received: 21.10.2002
Citation:
Lakdere Benkherouf, Vasyl Ustimenko, “Bounds for graphs of given girth and generalized polygons”, Algebra Discrete Math., 2002, no. 1, 1–18
Linking options:
https://www.mathnet.ru/eng/adm298 https://www.mathnet.ru/eng/adm/y2002/i1/p1
|
|