路和圈的极大分离集的数目

摘要

[目的]对路和圈这两类特殊图的极大分离集的数目进行研究.[方法]记MD（G）为图G的所有极大分离集构成的集合，?（G）为这个集合的基数.根据极大分离集的定义，对任意的点v∈V（G）,有■通过运用这个公式，分别求出路和圈的极大分离集数目的表达式；对阶数n用归纳法，比较路和圈的极大分离集数目的大小关系.[结果]对n≥6的路P_n,其极大分离集的数目满足关系?（P_n）=?(P_n-2)+?(P_n-3)+?(P_n-4)-?(P_n-6);对n≥11的圈C_n,其极大分离集的数目满足关系?（C_n）=?(C_n-2)+?(C_n-3)+?(C_n-4)-?(C_n-6);当n≥4且n≠6时，路和圈的极大分离集的数目满足关系?（C_n）≥?(P_n-1)+1.[结论]分别给出了路和圈的极大分离集数目的表达式，比较了二者的大小关系，这丰富了图的极大分离集的计数问题的结果.

关键词

路 / 圈 / 分离集 / 极大分离集