论文部分内容阅读
近五十年来,随着计算机科学和互联网技术的发展,图论得到了广泛的重视.各种形式的覆盖问题成为图论领域重要的研究方向.覆盖问题在VLSI设计(超大规模集成电路设计)、程序测试、网络问题、环协议、代码优化等方面有着广泛应用.本文主要研究图的路覆盖问题.给定一个图G=(V,E)和图G中路的集合p={P1,P2,…,Pr},定义Pi=(Vi,Ei),1≤i≤r,若路集合p满足：(1)Vi∩Vj=(?),i≠j；(2)Uir=1 Vi=V,则称路集合P是图G的一个路覆盖.最小路覆盖的基数称为图G的最小路覆盖数,记为c(G).路覆盖问题就是寻找图G中有c(G)条路的路覆盖.在本文第一部分里,我们给出了顶点数大于1的树T路覆盖数的下界p-eh-1,其中p表示叶子数,eh表示连接两个度大于2的顶点的边数.第二部分,我们得到了块图G与块-割点-树(block-cutpoint-tree) TG的最小路覆盖数之间的关系,从而给出了一类终端块数为b的块图的最小路覆盖数是b-1,其中终端块是割点数等于1的块.此外,对于一些特殊树状图,我们得到了其最小路覆盖数的精确值.最后,我们把关于树状图路覆盖数的结果应用到图的L(2,1)-标号问题和Hamiltonian completion问题上.得到了一些图的L(2,1)-标号数入(G)、洞指标ρ(G)和Hamiltonian completion问题的hc(G)的精确值.