论文部分内容阅读
令有n个顶点的图G的列表色数为x1·假设给图G的每个顶点都安排一个有t种颜色的列表.Albertson，Grossman和Haas[6]假设至少有tn/xl个顶点可被列表中颜色着色.第三章中，我们证明了该假设对于特征树是满k-叉树的Halin图是成立的. 图G是一个有n≥2个顶点的连通图，整数k≥1.假设图G的顶点v起火，消防员每次保护k个未被点燃的顶点，然后火与消防员在图上交替地移动.某顶点一旦被消防员选择，它就被视为已保护且不能再被点燃.在消防员移动后，火势从已着火的顶点蔓延至它的所有还未点燃的邻点.令snk(v)表示当火从顶点v着起时消防员可以保护图G的顶点个数的最大值.图G的k-生存率ρk(G)=∑v∈V(G) snk(v)/n2，表示被保护顶点个数的平均值.在第四章中，我们证明了:若PH是一个有n个顶点的伪-Halin图，那么ρ3(PH)＞1-√2/n，进一步推出limn→∞ρ3（PH）=1.