Exact generalized Turán numbers for even linear forests

Ya Hong Chen, Jia Bao Yang, Long Tu Yuan, Ping Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

An even linear forest is a graph whose connected components are all paths of even order. We characterize n-vertex graphs with maximum number of s-cliques and without containing an even linear forest for all values of n. Since a matching is an even linear forest, our result can be viewed as a generalization of the well-known Erdős-Gallai theorem (Erdős and Gallai, 1959 [3]). Moreover, our proof gives a new proof of a result of Wang (2020) [6].

Original languageEnglish
Article number113974
JournalDiscrete Mathematics
Volume347
Issue number7
DOIs
StatePublished - Jul 2024

Keywords

  • Even linear forests
  • Generalized Turán number

Fingerprint

Dive into the research topics of 'Exact generalized Turán numbers for even linear forests'. Together they form a unique fingerprint.

Cite this