论文部分内容阅读
令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了 k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了N(G,Kt)≤(n-k)(kt-1)+(kt).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了N(G,Ks,t)≤{(ks)(n-ss)-1/2(ks)(k-ss),t=s,(ks)(n-st)+(kt)(n-ts)-(kt)(k-ts),t≠s.rn此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数,记ν(G),(K)(G)分别为图G的最大匹配数和最小点覆盖.证明了当ν(G)≤k,(K)(G)= k+r 且 n≥2k+2r2+r+1 时,有e(G)≤(k+r+12)+(k-r)(n-k-r-1).