摘要
m-K_n-残差图是由P.Erds,F.Harary和M.Klawe等人提出的,当m=1时,他们证明了当n≠1,2,3,4时,K_(n+1)×K_2是唯一的具有最小阶的连通的K_n-残差图.首先得到了m-K_n-残差图的重要性质,同时证明了当n=1,2,3,4时,连通K_n-残差图的最小阶和极图,其中当n=1,2时得到唯一极图;当n=3,4时,证明了恰有两个不同构的极图,从而彻底解决连通的K_n-残差图的最小阶和极图问题.最后证明了当n≠1,2,3,4时,K_(n+1)×K_2是唯一的具有最小阶的连通的K_n-残差图.
The definition of m-Kn-residual graph was raised by P.Erdos,F.Harary and M.Klawe.When n ≠ 1,2,3,4,they proved that K（n＋1）×K2 is only connected to Kn-residual graph which has minimum order.In this paper,we have studied m-Knresidual graph,and obtained some important properties.At the same time,we proved that the connected Kn-residual graph of the minimum order and the extremal graph for n = 1,2,3,4.When n = 1,2,it is the only extremal graph.When n = 3,4,we proved just two connected residual graph non isomorphic with the minimum order,so as to thoroughly solve the connected Kn-residual graph of the minimum order and extremal graph＇s problems.Finally we prove that K（n＋1）×K2 is only connected with the minimum order of Kn-residual graph,when n ≠ 1,2,3,4.
出处
《运筹学学报》
CSCD
北大核心
2016年第2期38-48,共11页
Operations Research Transactions
基金
国家自然科学基金(No.61472056)
重庆市自然科学基金(Nos.cstc2015jcyjA00034
cstc2015jcyjA00015)
重庆市教委科研项目(Nos.KJl5012024
KJ1500403
KJ1400426)
关键词
残差图
最小阶
极图
residual graph
minimum order
extremal graph
