An extremal problem on the potentially \(P_k\)-graphic sequences
type: Item
instance of: scholarly article
title: An extremal problem on the potentially \(P_k\)-graphic sequences
zbMATH Open document ID: 0944.05024
DOI: 10.1016/S0012-365X(99)00289-7
author: Z. X. Song
author: Jiongsheng Li
published in: Discrete Mathematics
publication date: 2000-09-15T00:00:00Z
review text: A nonincreasing sequence \(\pi\) of \(n\) positive integers is potentially \(P_k\)-graphic if it is the degree sequence of some simple graph \(G\) of order \(n\) that contains a \(K_k\) as a subgraph. Denote \(\sigma(\pi)\) the sum of the terms of \(\pi\), and denote \(\sigma(k, n)\) the smallest \(\sigma(\pi)\) such that every \(\pi\) with \(\sigma(\pi) \geq \sigma(k,n)\) is potentially \(P_k\)-graphic. P. Erdős et al. (1991) conjectured that \(\sigma(k,n) = (k-1)(2n-k) + 2\). It is proved in this paper that (i) if \(k+1 \leq n \leq 2k\), then \(\sigma(k,n) = (k-1)(2n-k) + (n-k)(n-k-1) + 2\); and (ii) if \(n = 2k+1\), then \(\sigma(k,n) = (k-1)(2n-k) + k(k-1) + 2\). It is also proved that if \(n \geq 8\) then \(\sigma(3,n) = 4n-4\).
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1421658
zbMATH Keywords: potentially \(P_k\)-graphic
zbMATH Keywords: degree sequences
zbMATH Keywords: clique
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1421658