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,\dots ,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.