On Graphs with Adjacent Vertices of Large Degree

L. Caccetta1, P. Erdés2, K. Vijayan3
1School of Mathematics and Statistics Curtin University of Technology Perth, 6001 WESTERN AUSTRALIA
2Mathematical Institute Hungarian Academy of Sciences Budapest, HUNGARY
3Department of Mathematics University of Wester Australia Nedlands, 6009 WESTERN AUSTRALIA

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.