Turán numbers for disjoint paths

  • Long Tu Yuan
  • , Xiao Dong Zhang*
  • *Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

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 languageEnglish
Pages (from-to)499-524
Number of pages26
JournalJournal of Graph Theory
Volume98
Issue number3
DOIs
StatePublished - Nov 2021

Keywords

  • Turán number
  • disjoint path
  • extremal graph

Fingerprint

Dive into the research topics of 'Turán numbers for disjoint paths'. Together they form a unique fingerprint.

Cite this