蕴含K_(p,1,1,...,1)可图度序列  

Potentially K_(p,1,1,...,1) -graphic degree sequences

作　　者：赖春晖[1] 

机构地区：[1]漳州师范学院数学系,福建漳州363000

出　　处：《漳州师范学院学报（自然科学版）》2004年第4期11-13,共3页Journal of ZhangZhou Teachers College（Natural Science)

基　　金：国家自然科学基金资助项目(10271105) ;福建省‘百千万人才工程’人选培养资金资助项目;福建省科技项目;福建省教育厅科研项目及漳州师范学院科研项目资助

摘　　要：设 S 是 n 项可图序列, σ(S) 是 S 中的所有项之和, 设 H 是一个简单图, σ(H,n)是使得任意 n 项可图序列满足 σ(S) ≥ m , 则 S 有一个实现包含 H 作为子图的 m 的最小值, 本文给出了 σ(K p,1,1,...,1,n) 的下界并猜测对于所有的 n ≥ (t2 ) + 3p 此下界是可达到的.A sequence S is potentially K p,1,1,L,1 graphical if it has a realization containing a K p,1,1,L,1as a subgraph, where K p,1,1,L,1is a complete (t +1) -partite graph with partition sizes p,1,1,K,1.Let σ (K p,1,1,...,1,n) denote the smallest degree sum such that every n ? term graphical sequences S with σ(S) ≥ σ(Kp ,1,1,...,1,n) is potentially K p,1,1,L,1 graphical. In this paper, we prove that σ (K p,1,1,...,1,n) ≥ 2[( (p + 2t ? 3)n + p + 2t +1? pt ? t2 )/2]. We conjecture that the equality holds for n ≥ (t2 ) + 3p . +1

关 键 词：度序列 简单图 下界 子图 最小值 猜测 

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