The Maximum Number of Stars in a Graph Without Linear Forest

被引：0
|
作者：
Huang, Sumin [1 ]
Qian, Jianguo [1 ]
机构：
[1] Xiamen Univ, Sch Math Sci, Xiamen 361005, Peoples R China
来源：
GRAPHS AND COMBINATORICS | 2022年 / 38卷 / 06期
基金：
中国国家自然科学基金;
关键词：
Turan number; Generalized Turan number; Star; Linear forest; TURAN NUMBER; COPIES;
D O I：
10.1007/s00373-022-02580-1
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
For two graphs J and H, the generalized Turan 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 ex(n, S-r, F) when n is large enough, which generalizes the results on ex(n, S-r, P-k) and ex(n, (k + 1)P-2). Finally, we prose a problem related to the number of graph copies in an F-free graph under shifting operations.
引用
收藏
页数：12
相关论文
共 50 条
  • [31] Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
    Lin, Min-Sheng
    Chen, Yung-Jui
    INFORMATION PROCESSING LETTERS, 2008, 107 (06) : 257 - 264
  • [32] The maximum size of an induced forest in the binomial random graph
    Akhmejanova, Margarita
    Kozhevnikov, Vladislav
    DISCRETE MATHEMATICS, 2024, 347 (07)
  • [33] The maximum number of copies of an even cycle in a planar graph
    Lv, Zequn
    Gyori, Ervin
    He, Zhen
    Salia, Nika
    Tompkins, Casey
    Zhu, Xiutao
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 167 : 15 - 22
  • [34] Maximum Size of a Graph with Given Fractional Matching Number
    Ma, Tianlong
    Qian, Jianguo
    Shi, Chao
    ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (03):
  • [35] The Number of Independent Sets in a Graph with Small Maximum Degree
    David Galvin
    Yufei Zhao
    Graphs and Combinatorics, 2011, 27 : 177 - 186
  • [36] On the maximum average degree and the incidence chromatic number of a graph
    Dolama, MH
    Sopena, E
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2005, 7 (01): : 203 - 216
  • [37] The Number of Circles of a Maximum State of a Plane Graph with Applications
    Xian-an JIN
    Jun GE
    Xiao-Sheng CHENG
    Yu-qing LIN
    ActaMathematicaeApplicataeSinica, 2021, 37 (02) : 409 - 420
  • [38] The maximum number of paths of length four in a planar graph
    Ghosh, Debarun
    Gyori, Ervin
    Martin, Ryan R.
    Paulos, Addisu
    Salia, Nika
    Xiao, Chuanqi
    Zamora, Oscar
    DISCRETE MATHEMATICS, 2021, 344 (05)
  • [39] The distribution of the maximum number of common neighbors in the random graph
    Rodionov, I. V.
    Zhukovskii, M. E.
    EUROPEAN JOURNAL OF COMBINATORICS, 2023, 107
  • [40] The maximum number of paths of length three in a planar graph
    Grzesik, Andrzej
    Gyori, Ervin
    Paulos, Addisu
    Salia, Nika
    Tompkins, Casey
    Zamora, Oscar
    JOURNAL OF GRAPH THEORY, 2022, 101 (03) : 493 - 510
12345