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 等数据库收录! |
|