Ramsey theory and strength of graphs

Abstract

A numbering $f$ of a graph $G$ of order $n$ is a labeling that assigns distinct elements of the set $\left\{1,2,\dots ,n\right\}$ to the vertices of $G$, where each $uv\in E\left(G\right)$ is labeled $f\left(u\right)+f\left(v\right)$. The strength $\mathrm{str}\left(G\right)$ of $G$ is defined by $\mathrm{str}\left(G\right)=\min \left\{{\mathrm{str}}_f\left(G\right)|f\text{ is a numbering of }G\right\}$, where ${\mathrm{str}}_f\left(G\right)=\max \left\{f\left(u\right)+f\left(v\right)|uv\in E\left(G\right)\right\}$. Let $f\left(n\right)$ denote the maximum of $\mathrm{str}\left(G\right)+$ over nonempty graphs $G$ and of order $n$, where $\overline{G}$ represents the complement of $G$. In this paper, we establish a lower bound for the Ramsey numbers related to the concept of strength of a graph and show a sharp lower bound for $f\left(n\right)$. In addition to these results, we provide another lower bound and remark some exact values for $f\left(n\right)$. Furthermore, we extend existing necessary and sufficient conditions involving the strength of a graph. Finally, we investigate bounds for $\mathrm{str}\left(G\right)+\mathrm{str}\left(\overline{G}\right)$ whenever $G$ and $\overline{G}$ are nonempty graphs of order $n$. Throughout this paper, we propose some open problems arising from our study.