| 摘要: |
| 给定一个图$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$, 并给出边数最少的哈密顿路径饱和图的一种构造方法. |
| 关键词: 饱和图 饱和数 极值图 哈密顿路径 |
| DOI：10.3969/J.ISSN.1000-5137.2022.03.009 |
| 分类号:O241 |
| 基金项目:国家自然科学基金面上项目(11971319) |
|
| On the saturation number of Hamiltonian path |
|
DING Tianping, JIN Yalei, ZHANG Qian
|
|
Mathematics and Science College, Shanghai Normal University, Shanghai 200234, China
|
| Abstract: |
| 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$. |
| Key words: saturated graph saturation number extremum graph Hamiltonian path |
