首页 | 本学科首页   官方微博 | 高级检索  
     


The smallest degree sum that yields potentially Kr,r-graphic sequences
Authors:Jianhua Yin and Jiongsheng Li
Affiliation:(1) Department of Mathematics, University of Science and Technology of China, 230026 Hefei, China
Abstract:We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(Kr,r,n) such that every n-term graphic sequence π = (d1,d2,...,dn) with term sum σ(π) = d1 + d2 + ... + dn ≥ σ(Kr,r,n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. π has a realization G containing Kr,r as its subgraph. In this paper, the values σ(Kr,r,n) for even r and n ≥ 4r2 - r - 6 and for odd r and n ≥ 4r2 + 3r - 8 are determined.
Keywords:graph  degree sequence  potentially Kr,r-graphic sequence
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号