树的3—路图的Hamiltonian性

• 作 者: 徐军 王朝瑞
• 机 构: 北京理工大学应用数学系,北京理工大学应用数学系北京100081,北京100081
• 出 处: 北京理工大学学报
• 发表日期: 1993年4期
• 关键词: k-路图 树 单圈图 哈密顿图 trees (mathematics)/single cycle graph k-path graph Hamiltonia
• 基金项目: 国家自然科学基金资助项目

一个图G的k-路图P_k（G）是指以G的长为（K-1）的路为点集.在P_K（G）中两个点邻接当且仅当其并是G的长为k的路或长为k的圈.本文解决了H.J.Broersma和C.Hoede提出的两个关于3-路图的猜想:①若树T满足Δ（T）≥4,则其3-路图P₃（T）是非Hamiltonian的.②若G是单圈图,且Δ（G）≥5,则其3-路图P<sub>3</su