顶点覆盖k-路问题(VCPk)是找一个最小的顶点子集,使得图中每一条k一路都至少有一个顶点在这个顶点子集中。这个问题是经典的顶点覆盖问题的推广,在无线传感器网络加密和摄像头安置等实际生活中有着广泛的应用。顶点覆盖k-路问题是一个NP困难的问题,本文考虑了它在特殊图上的算法,给出了单圈图上顶点覆盖k-路问题的多项式时间内的有效算法,证明了三正则图上顶点覆盖4-路问题是NP困难的,并给出了一个2-近似算法。富勒烯是一种完全由碳构成的,形状为空心球体、椭圆状或管状的分子。一直以来,碳的同素异形体都被限制在石墨、金刚石和诸如煤、木炭等物质,富勒烯的发现大大扩展了已知的碳的同素异形体的数目。研究它的化学和物理性质是目前的热点问题,许多物理学者、化学学者和数学学者广泛参与了这些研究。本文主要从图的一些参数的角度研究了富勒烯图,探讨了(5,6)-富勒烯图上的低阶路径、匹配和独立集的数目和(4,6)-富勒烯图上的5-匹配的数目,分别给出了确定的计算公式。