退化图中的子图计数问题研究

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

Study on the Counting of Subgraphs in Degenerate Graph

Let G be a graph of n vertices.A graph is k-degenerate if every subgraph of it contains a vertex of degree at most k.Let N(G,F) represent the number of F subgraphs in the graph G.This paper mainly studies the problem of counting of the complete subgraph and complete bipartite subgraph in the k-degenerate graph and gives the upper bound of counting and the corresponding extremal graph.First,we prove Ν(G,K_t)≤(n-k)(k t-1)+(k t). Second,if s,t≥1,n≥k+1 and s+t≤k,we prove Ν(G,K_s,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s. Moreover,we also study the number of edges in the graph G when the maximum matching and minimum vertex coverage are determined.Let v(G),K(G) be the maximum matching number and minimum vertex coverage of the graph G,respectively.We prove v(G) ≤ k,K(G)=k+r and n≥2 k+2 r²+r+1,then e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).