Pure and Applied Mathematics Quarterly

Volume 18 (2022)

Number 6

Special issue in honor of Fan Chung

Guest editors: Paul Horn, Yong Lin, and Linyuan Lu

Singular Turán numbers of stars

Pages: 2599 – 2618

DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a12

Authors

Gaoxing Sun (Center for Discrete Mathematics, Fuzhou University, Fuzhou, China)

Heng Li (Center for Discrete Mathematics, Fuzhou University, Fuzhou, China)

Qinghou Zeng (Center for Discrete Mathematics, Fuzhou University, Fuzhou, China)

Jianfeng Hou (Center for Discrete Mathematics, Fuzhou University, Fuzhou, China)

Abstract

Suppose that $G$ is a graph and $H$ is a subgraph of $G$. We call $H$ singular if the vertices of $H$ either have the same degree in $G$ or have pairwise distinct degrees in $G$. Let $T_S (n, H)$ be the largest number of edges of a graph with $n$ vertices that does not contain a singular copy of $H$. The problem of determining $T_S (n, H)$ was studied initially by Caro and Tuza, who obtained an asymptotic bound for each $H$. In this paper, we consider the case that $H$ is a star, and determine the exact values of $T_S (n, K_{1,2})$ for all $n$, $T_S (n, K_{1,4})$ and $T_S (n, K_{1,2s+1})$ for sufficiently large $n$.

Keywords

singular, Turán number, star, $H$-free

2010 Mathematics Subject Classification

05C07, 05C35

Received 30 June 2021

Received revised 1 March 2022

Accepted 3 May 2022

Published 29 March 2023