Turán numbers for disjoint paths
Long‐Tu Yuan, Xiao‐Dong Zhang
Abstract
Abstract The Turán number of a graph , ex, is the maximum number of edges in a graph of order that does not contain a copy of as a subgraph. Lidický, Liu and Palmer determined ex for sufficiently large and proved that the extremal graph is unique, where is the union of pairwise vertex‐disjoint paths on vertices. There are a few kinds of graphs for which ex are known exactly for all , 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 for all integers when at most one of is odd. Furthermore, we show that there exists a family of pairs of bipartite graphs such that for all integers , which is related to an old problem of Erdős and Simonovits.