An extremal problem on potentially Kr,s-graphic sequences |
| |
Authors: | Jian-Hua Yin Jiong-Sheng Li |
| |
Institution: | a Department of Mathematics, University of Science and Technology of China, Hefei, Anhui 230026, People's Republic of China b Department of Mathematics, Quanzhou Teachers College, Quanzhou, Fujian 362000, People's Republic of China |
| |
Abstract: | We consider a variation of a classical Turán-type extremal problem (F. Chung, R. Graham, Erd
s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(Kr,s,n) such that every n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2++dnσ(Kr,s,n) is potentially Kr,s-graphic, where Kr,s is a r×s complete bipartite graph, i.e., π has a realization G containing Kr,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially Kr,s-graphic, and then we determine σ(Kr,r,n) for r=3,4. |
| |
Keywords: | Graph Degree sequence Potentially Kr s-graphic sequence |
本文献已被 ScienceDirect 等数据库收录! |
|