Extremal graphs of order dimension 4

  • Geir Agnarsson

Abstract

We study the maximal number of edges of a graph on $p$ vertices of order dimension 4. We will show that the lower bound for this number is greater than $\frac{3}{8}p^{2} + 2p - 13$. In particular the Turn-4 graph on $p$ vertices does not have the maximal number of edges among the graphs of order dimension 4.
Published
2002-03-01
How to Cite
Agnarsson, G. (2002). Extremal graphs of order dimension 4. MATHEMATICA SCANDINAVICA, 90(1), 5-12. https://doi.org/10.7146/math.scand.a-14358
Section
Articles