哈密顿路径的饱和数

On the saturation number of Hamiltonian path

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

Let F be a graph and graph G is said to be F-saturated if G is F-free.However,for any edge e∈E(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))=[3n−2/2],where n∈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≥22.