Abstract
The Turán number of a graph (Formula presented.), ex (Formula presented.), is the maximum number of edges in a graph of order (Formula presented.) that does not contain a copy of (Formula presented.) as a subgraph. Lidický, Liu and Palmer determined ex (Formula presented.) for sufficiently large (Formula presented.) and proved that the extremal graph is unique, where (Formula presented.) is the union of pairwise vertex-disjoint paths on (Formula presented.) vertices. There are a few kinds of graphs (Formula presented.) for which ex (Formula presented.) are known exactly for all (Formula presented.), including cliques, matchings, paths, cycles on odd number of vertices and some other special graphs. In this paper, using a different approach from Lidický, Liu and Palmer, we determine ex (Formula presented.) for all integers (Formula presented.) when at most one of (Formula presented.) is odd. Furthermore, we show that there exists a family of pairs of bipartite graphs (Formula presented.) such that (Formula presented.) for all integers (Formula presented.), which is related to an old problem of Erdős and Simonovits.
| Original language | English |
|---|---|
| Pages (from-to) | 499-524 |
| Number of pages | 26 |
| Journal | Journal of Graph Theory |
| Volume | 98 |
| Issue number | 3 |
| DOIs | |
| State | Published - Nov 2021 |
Keywords
- Turán number
- disjoint path
- extremal graph