The smallest degree sum that yields potentially kCℓ-graphic sequences |
| |
Authors: | Jian-Hua Yin Jiong-Sheng Li Guo-Liang Chen |
| |
Affiliation: | aDepartment of Mathematics, Hainan University, Haikou, Hainan 570228, China bDepartment of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui 230027, China cDepartment of Mathematics, University of Science and Technology of China, Hefei, Anhui 230026, China |
| |
Abstract: | Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2++dnσ(H,n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3kℓ, we completely determine the smallest even integer σ(kCℓ,n) such that each n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2++dnσ(kCℓ,n) has a realization G containing a cycle of length r for each r, krℓ. |
| |
Keywords: | Graph Degree sequence Potentially kCℓ-graphic sequence |
本文献已被 ScienceDirect 等数据库收录! |
|