蕴含K3,s-ke的可图序列

Potentially K3, s-ke Graphical Sequences

关键词:  图  度序列  蕴含  几乎完全二部图

Key words:  graph  degree sequence  potentially  almost complete bipartite graph

摘要:

考虑经典Turán型问题的变形:确定最小的正偶数σ(K_r,s-ke,n),s ≥ r ≥ k ≥ 1,使得对于每一个n项可图序列π=(d₁,d₂,…,d_n),当σ(π)=d₁+d₂+…+d_n ≥ σ(K_r,s-ke,n)时,π是蕴含几乎完全二部图K_r,s-ke可图的,即K_r,s-ke是从完全二部图K_r,s中删去k条边后所得的图,而这k条边构成K_r,s的一匹配.然后确定出当r=3,s ≥ 4且n充分大时,σ(K_r,s-ke,n)的值.

Abstract:

In this paper, we consider a variation of the classical Turán-type extremal problems as follows:determine the smallest positive even number σ (K_{r, s}-ke, n), s ≥ r ≥ k ≥ 1, such that every n term graphic sequence π= (d₁, d₂, …, d_n) with term sum σ (π)=d₁+d₂+…+d_n ≥ σ (K_{r, s}-ke, n) is potentially K_{r, s}-ke-graphic, where K_{r, s}-ke is an almost complete bipartite graph that obtained from a complete bipartite graph K_{r, s} by deleting k edges forming a matching.We determine the values of σ (K_{r, s}-ke, n) for r=3, s ≥ 4 and sufficiently large n.