Graphic Sequences with a Realization Containing a Friendship Graph

Abstract

For any simple graph \(H\), let \(\sigma(H, n)\) be the minimum \(m\) so that for any realizable degree sequence \(\pi = (d_1, d_2, \ldots, d_n)\) with sum of degrees at least \(m\), there exists an \(n\)-vertex graph \(G\) witnessing \(\pi\) that contains \(H\) as a weak subgraph. Let \(F_{k}\) denote the friendship graph on \(2k+1\) vertices, that is, the graph of \(k\) triangles intersecting in a single vertex. In this paper, for \(n\) sufficiently large, \(\sigma(F_{k},n)\) is determined precisely.