运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2014年
2期
59-68
,共10页
残差图%最小阶%同构
殘差圖%最小階%同構
잔차도%최소계%동구
residually graph%minimum order%isomorphic
Erd(o)s P,Harary F和Klawe M研究了Kn-残差图,并对连通的m-Kn-残差图提出了一些结论和猜想.利用容斥原理以及集合的运算性质等方法,研究了连通的3-Kn-残差图,得到当顶点最小度为n时,3-Kn-残差图最小阶的计算公式以及相应的唯一极图.当n=2时,得到最小阶为11以及相应的极图;当n=3时,得到最小阶为20并找到两个不同构的极图,不满足Erd(o)s等提出的结论;当n=4时,得到最小阶为22及相应的极图;当n=8时,可以找到两个不同构的3-K8-残差图,不满足Erd(o)s等提出的结论;最后证明了当n=9,10时,最小阶分别为48和52以及相应的唯一极图,验证了Erd(o)s等在文献(Residually-complete graphs [J].Annals of Discrete Mathematics,1980,6:117-123)中提出的结论.
Erd(o)s P,Harary F和Klawe M研究瞭Kn-殘差圖,併對連通的m-Kn-殘差圖提齣瞭一些結論和猜想.利用容斥原理以及集閤的運算性質等方法,研究瞭連通的3-Kn-殘差圖,得到噹頂點最小度為n時,3-Kn-殘差圖最小階的計算公式以及相應的唯一極圖.噹n=2時,得到最小階為11以及相應的極圖;噹n=3時,得到最小階為20併找到兩箇不同構的極圖,不滿足Erd(o)s等提齣的結論;噹n=4時,得到最小階為22及相應的極圖;噹n=8時,可以找到兩箇不同構的3-K8-殘差圖,不滿足Erd(o)s等提齣的結論;最後證明瞭噹n=9,10時,最小階分彆為48和52以及相應的唯一極圖,驗證瞭Erd(o)s等在文獻(Residually-complete graphs [J].Annals of Discrete Mathematics,1980,6:117-123)中提齣的結論.
Erd(o)s P,Harary F화Klawe M연구료Kn-잔차도,병대련통적m-Kn-잔차도제출료일사결론화시상.이용용척원리이급집합적운산성질등방법,연구료련통적3-Kn-잔차도,득도당정점최소도위n시,3-Kn-잔차도최소계적계산공식이급상응적유일겁도.당n=2시,득도최소계위11이급상응적겁도;당n=3시,득도최소계위20병조도량개불동구적겁도,불만족Erd(o)s등제출적결론;당n=4시,득도최소계위22급상응적겁도;당n=8시,가이조도량개불동구적3-K8-잔차도,불만족Erd(o)s등제출적결론;최후증명료당n=9,10시,최소계분별위48화52이급상응적유일겁도,험증료Erd(o)s등재문헌(Residually-complete graphs [J].Annals of Discrete Mathematics,1980,6:117-123)중제출적결론.
