论文部分内容阅读
对于图G=(V(G),E(G)),令G的一个子图集B={H1,Hk},若G的每条边至少存在于一个Hi中,则称B为G的一个覆盖。若B中每个元都与图H同构,则称召为G的一个H-覆盖。 若存在双射f:V(G)∪E(G)→[1,|V(G)|+|E(G)|],使得对∨H∈B,∑u∈v(H)f(u)+∑e∈E(H)f(e)是常数,则称G是H-幻的,f为G的H-幻标号。若f(V(G))=[1,|V(G)|],则称G是H-超幻的,f为G的H-超幻标号。 超幻标号是图覆盖与标号相结合形成的新概念,在图论领域有着极其重要的地位。国内外许多学者都对超幻标号给予了很多的关注。在本文中,我们将利用代数与组合相结合的方法来研究超幻标号的问题。 文章共分三部分,第一部分介绍了标号的研究背景、基本概念和己知结果;第二部分利用直接构造和递归构造的方法得到了带有限制条件的集合分拆的结果,再将其应用到幻标号问题中,即得第三部分的两个重要定理: ·对任意的整数k≥3,n≥1,t≥0,Pk·(Cm+t)n是(Cm+t)-超幻的。 ·对任意的整数m≥2,n≥2,Pm×Pn是C4-超幻的。