图中控制数的有关结论

王春香

doi:10.19603/j.cnki.1000-1190.2009.01.002

华中师范大学学报（自然科学版） ›› 2009, Vol. 43 ›› Issue (01) : 4 -6+30. DOI: 10.19603/j.cnki.1000-1190.2009.01.002

图中控制数的有关结论

王春香

作者信息 +

Author information +

文章历史 +

PDF

摘要

令G=（V,E）是一个图,点集S■V,如果满足N[S]=V（G）(或N（S）=V（G）),则称点集S是一个控制集（或全控制集）.一个连通图G如果满足:对任何不相邻于一次点的点v,G-v的全控制数小于G的全控制数,则称图G是一个γ_t-临界图.给出了连通无爪3-正则图G的控制数满足γ（G）≤n/3.同时找到一个直径是2的4-γ_t-临界图.