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 language | English |
|---|---|
| Article number | 113974 |
| Journal | Discrete Mathematics |
| Volume | 347 |
| Issue number | 7 |
| DOIs | |
| State | Published - Jul 2024 |
Keywords
- Even linear forests
- Generalized Turán number