Tur{\'a}n numbers for wheels

Tomasz Dzido
University of Gdansk

Andrzej Jastrz\c{e}bski
Gda\'nsk University of Technology

PDF

Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

Content: The Tur{\'a}n number $ex(n, G)$ is the maximum number of edges in any $n$-vertex graph that does not contain a subgraph isomorphic to $G$. A \emph{wheel} $W_k$ is a graph on $k$ vertices obtained from a $C_{k-1}$ by adding one vertex $w$ and making $w$ adjacent to all vertices of the $C_{k-1}$. We obtain exact values for $ex(n, W_k)$ where $n \geq k$ and $k \leq 7$. It is interesting that exact values for $ex(n, C_4)$ and $ex(n, C_6)$, i.e.~for rims of wheels $W_{5}$ and $W_{7}$ remain unknown in general. Even in the case of the $C_{4}$ cycle values are known only for $n\leq 32$ (the last result being $ex(32, C_{4})=92$, obtained in 2009 by Shao, Xu and Xu), whereas for larger $n$ only the upper or lower bounds are known. In addition, we present some bounds in general case.

Back to all abstracts