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


The smallest degree sum that yields potentially Kr,r-graphic sequences
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. πr 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
本文献已被 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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