On Graphs with Adjacent Vertices of Large Degree

Abstract

Let $\mathcal{G}(n,m)$ denote the class of simple graphs on $n$ vertices and $m$ edges, and let $G\in \mathcal{G}(n,m)$. For suitably restricted values of $m$, $G$ will necessarily contain certain prescribed subgraphs such as cycles of given lengths and complete graphs. For example, if $m>\frac{1}{4}{n}^2$, then $G$ contains cycles of all lengths up to $\lfloor \frac{1}{2}(n+3)\rfloor$. Recently, we have established a number of results concerning the existence of certain subgraphs (cliques and cycles) in the subgraph of $G$ induced by the vertices of $G$ having some prescribed minimum degree. In this paper, we present some further results of this type. In particular, we prove that every $G\in \mathcal{G}(n,m)$ contains a pair of adjacent vertices each having degree (in $G$) at least $f(n,m)$ and determine the best possible value of $f(n,m)$. For $m>\frac{1}{4}{n}^2$, we find that $G$ contains a triangle with a pair of vertices satisfying this same degree restriction. Some open problems are discussed.