A note on the potential function of an arbitrary graph $H$

Jianhua Yin, Guangming Li


Given a graph $H$, a graphic sequence
$\pi$ is {\it potentially} $H$-{\it graphic} if there is a
realization of $\pi$ containing $H$ as a subgraph. In 1991,
Erd\H{o}s et al introduced the following problem:
determine the minimum even integer $\sg(H,n)$ such that each
$n$-term graphic sequence with sum at least $\sg(H,n)$ is
potentially $H$-graphic. This problem can be viewed as a
``potential" degree sequence relaxation of the Tur\'{a}n problems.
Let $H$ be an arbitrary graph of order $k$. Ferrara et al
[Combinatorica, 36(2016)687--702] established an upper bound on
$\sg(H,n)$: if $\omega=\omega(n)$ be an increasing function that
tends to infinity with $n$, then there exists an $N=N(\omega,H)$
such that $\sg(H,n)\le \widetilde{\sg}(H)n+\omega(n)$ for any $n\ge N$, where $\widetilde{\sg}(H)$ is a parameter only depending on the graph $H$. Recently, Yin [European J. Combin., 85(2020)103061]
obtained a new upper bound on $\sg(H,n)$: there exists an
$M=M(k,\alpha(H))$ such that $\sg(H,n)\le
\widetilde{\sg}(H)n+k^2-3k+4$ for any $n\ge M$. In this paper, we investigate the precise behavior of $\sg(H,n)$ for arbitrary $H$
with $\widetilde{\sg}_{\alpha(H)+1}(H)<\widetilde{\sg}(H)$ or
$\nabla_{\alpha(H)+1}(H)\ge 2$. Moreover, we also show that
$\sg(H,n)=(k-\alpha(H)-1)(2n-k+\alpha(H))+2$ for those $H$ so that $\nabla_{\alpha(H)+1}(H)=1$,
$\widetilde{\sg}_p(H)<\widetilde{\sg}(H)$ for $\alpha(H)+2\le p\le
k$ and there is an $F<H$ with $|V(F)|=\alpha(H)+1$ and


  • There are currently no refbacks.