A note on the potential function of an arbitrary graph H


Jianhua Yin, Guangming Li




Given a graph H, a graphic sequence pi is potentially H-graphic if there is a realization of pi containing H as a subgraph. In 1991, Erdős et al. introduced the following problem: determine the minimum even integer σ(H,n) such that each n-term graphic sequence with sum at least σ(H,n) is potentially H-graphic. This problem can be viewed as a “potential” degree sequence relaxation of the Tura´n problems. Let H be an arbitrary graph of order k. Ferrara et al. [Combinatorica, 36(2016)687–702] established an upper bound on σ(H,n): if ω = ω(n) is an increasing function that tends to infinity with n, then there exists an N = N(ω,H) such that σ(H,n) ≤ σ˜(H)n + ω(n) for any n ≥ N, where σ˜(H) is a parameter only depending on the graph H. Recently, Yin [European J. Combin., 85(2020)103061] obtained a new upper bound on σ(H,n): there exists an M = M(k, α(H)) such that σ(H,n) ≤ σ˜(H)n + k2 − 3k + 4 for any n ≥ M. In this paper, we investigate the precise behavior of σ(H,n) for arbitrary H with σ˜α(H)+1(H) < σ˜(H) or ∇α(H)+1(H) ≥ 2, where ∇α(H)+1(H) = min{∆(F)|F is an induced subgraph of H and |V(F)| = α(H) + 1} and σ˜α(H)+1(H) = 2(k−α(H)−1)+∇α(H)+1(H)−1. Moreover, we also show thatσ(H,n) = (k−α(H)−1)(2n−k+α(H))+2 for those H so that ∇α(H)+1(H) = 1, σ˜α(H)+1(H) = σ˜(H), σ˜p(H) < σ˜(H) for α(H) + 2 ≤ p ≤ k and there is an F < H with |V(F)| = α(H) + 1 and pi(F) = (12, 0α(H)−1)