A numbering $f$ of a graph $G$ of order $n$ is a labeling that assigns distinct elements of the set $\left\{ 1,2,\ldots ,n\right\} $ to the vertices of $G$. The strength $\textrm{ str}_{ f}\left( G\right)$ of a numbering $f:V\left( G\right) \rightarrow \left\{ 1,2,\ldots ,n\right\} $ of $G$ is defined by% \begin{ equation*} \mathrm{ str}_{ f}\left( G\right) =\max \left\{ f\left( u\right) +f\left( v\right) \left| uv\in E\left( G\right) \right. \right\} \text{ ,} \end{ equation*}% that is, $\mathrm{ str}_{ f}\left( G\right) $ is the maximum edge label of $G$ and the strength\ \textrm{ str}$\left( G\right) $ of a graph $G$ itself is \begin{ equation*} \mathrm{ str}\left( G\right) =\min \left\{ \mathrm{ str}_{ f}\left( G\right) \left| f\text{ is a numbering of }G\right. \right\} \text{ .} \end{ equation*} In this paper, we present a sharp lower bound for the strength of a graph in terms of its domination number as well as its (edge) covering and (edge) independence number. We also provide a necessary and sufficient condition for the strength of a graph to attain the earlier bound in terms of their subgraph structure. In addition, we establish a sharp lower bound for the domination number of a graph under certain conditions.
Categories: math.CO