# MathSciDoc: An Archive for Mathematician ∫

#### Combinatoricsmathscidoc:2402.06003

Ars Combinatoria, 94, 289-298, 2010.1
Let $K_k$, $C_k$, $T_k$, and $P_{k}$ denote a complete graph on $k$ vertices, a cycle on $k$ vertices, a tree on $k+1$ vertices, and a path on $k+1$ vertices, respectively. Let $K_{m}-H$ be the graph obtained from $K_{m}$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_{m}$). A sequence $S$ is potentially $K_{m}-H$-graphical if it has a realization containing a $K_{m}-H$ as a subgraph. Let $\sigma(K_{m}-H, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma(S)\geq \sigma(K_{m}-H, n)$ is potentially $K_{m}-H$-graphical. In this paper, we determine the values of $\sigma (K_{r+1}-H, n)$ for $n\geq 4r+10, r\geq 3, r+1 \geq k \geq 4$ where $H$ is a graph on $k$ vertices which contains a tree on $4$ vertices but not contains a cycle on $3$ vertices. We also determine the values of $\sigma (K_{r+1}-P_2, n)$ for $n\geq 4r+8, r\geq 3$.
graph; degree sequence; potentially $K_{r+1}-H$-graphic sequence
@inproceedings{lai2010an,
title={An Extremal Problem On Potentially $K_{r+1}-H$-graphic Sequences},
author={Lai Chunhui, and Hu Lili},
url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20240212155256160820766},
booktitle={Ars Combinatoria},
volume={94},
pages={289-298},
year={2010},
}

Lai Chunhui, and Hu Lili. An Extremal Problem On Potentially $K_{r+1}-H$-graphic Sequences. 2010. Vol. 94. In Ars Combinatoria. pp.289-298. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20240212155256160820766.