The maximum number of stars in a graph without linear forest

For two graphs \(J\) and \(H\), the generalized Tur\'{a}n number, denoted by \(ex(n,J,H)\), is the maximum number of copies of \(J\) in an \(H\)-free graph of order \(n\). A linear forest \(F\) is the disjoint union of paths. In this paper, we determine the number \(ex(n,S_r,F)\) when \(n\) is...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-12
Main Authors: Huang, Sumin, Qian, Jianguo
Format: Article
Language:English
Subjects:
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For two graphs \(J\) and \(H\), the generalized Tur\'{a}n number, denoted by \(ex(n,J,H)\), is the maximum number of copies of \(J\) in an \(H\)-free graph of order \(n\). A linear forest \(F\) is the disjoint union of paths. In this paper, we determine the number \(ex(n,S_r,F)\) when \(n\) is large enough and characterize the extremal graphs attaining \(ex(n,S_r,F)\), which generalizes the results on \(ex(n, S_r, P_k)\), \(ex(n,K_2,(k+1) P_2)\) and \(ex(n,K^*_{1,r},(k+1) P_2)\). Finally, we pose the problem whether the extremal graph for \(ex(n,J,F)\) is isomorphic to that for \(ex(n,S_r,F)\), where \(J\) is any graph such that the number of \(J\)'s in any graph \(G\) does not decrease by shifting operation on \(G\).
ISSN:2331-8422