✦ LIBER ✦
The smallest degree sum that yields potentiallyPk-graphical sequences
✍ Scribed by Jiong-Sheng, Li; Zi-Xia, Song
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 354 KB
- Volume
- 29
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
A simple graph G is said to have property P k if it contains a complete subgraph of order k + 1, and a sequence π is potentially P k -graphical if it has a realization having property P k . Let σ(k, n) denote the smallest degree sum such that every n-term graphical sequence π without zero terms and with degree sum σ(π) ≥ σ(k, n) is potentially P k -graphical. Erdös, Jacobson, and Lehel [Graph Theory, 1991, 439--449] conjectured that σ(k, n) = (k -1)(2n -k) + 2. In this article, we prove that the conjecture is true for k = 4 and n ≥ 10.