蕴含K_(r,s,t)可图序列的一个极值问题  

An Extremal Problem on the Potentially K_(r,s,t)-Graphic Sequences

作　　者：陈纲[1] 

机构地区：[1]宁夏大学数学计算机学院,宁夏银川750021

出　　处：《烟台大学学报（自然科学与工程版）》2006年第4期245-252,共8页Journal of Yantai University(Natural Science and Engineering Edition)

摘　　要：Gou ld,Jacobson和Lehe l考虑了下述经典Turán型极值问题的一个变形:对于给定的图H,确定最小的偶数σ(H,n),使得每一个n项可图序列π=(d1,d2,…,dn),当σ(π)=d1+d2+…+dn≥σ(H,n)时,π都有一个实现G包含H作为子图.本文确定了σ(K1,2,2,n),8≥n≥5,及当n≥6时,σ(K2,2,2,n)之值,其中Kr,s,t是r×s×t完全三部图.Gould, Jacobson and Lehel considered a variation of the classical Turan-type extremal problems： for a given graph H, determine the smallest even integer σ （H, n） such that each n -term graphic sequence π = （d1 ,d2 ,... ,dn） with σ（π） = d1 ＋ d2 ＋ ... ＋ d. ≥σ （H,n） has a realization G containing H as a subgraph. In this paper, the values of σ（K1,2,2 ,n） for 8 ≥ n ≥ 5 and σ（K2.2,2 ,n） for n ≥ 6 are determined, where Kr is the r x s x t complete 3-partite graph.

关 键 词：图 度序列 蕴含Kr s t 可图序列 

分 类 号：O157.5[理学—数学]