哈密顿路径的饱和数

给定一个图$F$, 如果图$G$中不包含$F$，且在$G$中添加图$G$的补图$\overline{G}$的任意一条边$e$后得到的图$G+e$中包含$F$, 则称图$G$为$F$-饱和图. 设sat($n,F$)=min{|$E(G)$|:|$V(G)$|=$n$，$G$是$F$-饱和图. 证明了当$n\in K=\{34,35,36,37,44,45,52,53\}$时都有sat($n,P_{n}$)=$\left\lceil \frac{3n-2}{2} \right\rceil$, 并给出边数最少的哈密顿路径饱和图的一种构造方法.

On the saturation number of Hamiltonian path

Let $F$ be a graph and graph $G$ is said to be $F$-saturated if $G$ is $F$-free.However, for any edge $e\in E(\overline{G})$, $G+e$ contains $F$.Let sat($n,F$)= min{|$E(G)$|:|$V(G)$|=$n$ and $G$ is $F$-saturated}. We will show that there exists sat($n,P_{n}$)=$\left\lceil \frac{3n-2}{2} \right\rceil$,where $n\in K=\{34,35,36,37,44,45,52,53\}$, and we will construct a group of hamiltonian path saturated graphs with the smallest size of order $n$, for $n\geq 22$.