The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number

作者：Liu, Yuxuan; Zhang, Leilei^*

来源：Discrete Mathematics, 2024, 347(1): 113734.

DOI：10.1016/j.disc.2023.113734

• Circumference
• Matching number
• Complete multipartite graph
• Generalized Turan number

The circumference c(G) of a graph G is the length of a longest cycle in G and the matching number alpha'(G) is the maximum size of a matching in G. In 1959, Erdos and Gallai determined the maximum size of graphs with given c(G) or alpha'(G). Let K-r1,K- (...,rs) denote the complete multipartite graph with class sizes r(1,) (..., rs) and delta(G) be the minimum degree of G. In this paper, we determine the maximum number of copies of K-r1,K- ...,K-rs in a 2-connected n-vertex graph G with given c(G) and delta(G) >= k. The corresponding problem for an n-vertex graph G with given alpha'(G) and delta(G) >= k is also addressed. As a corollary of our main results, we determine the maximum number of copies of K-r1,K- ...,K-rs in an n-vertex graph with given c(G) or alpha'(G). In addition, the corresponding problems for graphs with given detour order are solved as well.