摘要
研究了盒子中的蛇问题 ,即求n方体Qn 中最大导出环Sn 问题 ;已知｜S2 ｜ =4,｜S3 ｜ =6 ,｜S4 ｜=8,｜S5｜=14,｜S6｜=2 6 .通过回溯算法证明了｜S7｜=48,｜S8｜≥ 94,并给出猜想 ｜Sn｜≤ 2｜Sn-1｜- 2 (n≥ 3) .该猜想对 3≤n≤ 7已成立 .
Let S n denote the longest induced cycle in Q n . It is kwown that ｜S 2｜=4, ｜S 3｜=6, ｜S 4｜=8, ｜S 5｜=14, ｜S 6｜=26 . It is shown that ｜S 7｜=48, ｜S 8｜≥94 by a search backward algorithm. A conjecture is given that |S n|≤2|S n-1 |-2 (n≥3) . It is proved for 3≤n≤7 .
出处
《大连理工大学学报》
CAS
CSCD
北大核心
2000年第5期509-511,共3页
Journal of Dalian University of Technology
基金
国家自然科学基金!资助项目 ( 69473 0 3 1)
关键词
无向图
最大导出环
回溯算法
undirected graph
isomorphism of graphs/ n cube Q n
the largest induced cycle
