Minimum degree and size conditions for the proper connection number of graphs

Abstract

An edge-coloured graph $G$ is called $properly$ $connected$ if every two vertices are connected by a proper path. The $proper$ $connection$ $number$ of a connected graph $G$, denoted by $pc(G)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Susan A. van Aardt et al. gave a sufficient condition for the proper connection number to be at most $k$ in terms of the size of graphs. In this note, %optimizes the boundary of the number of edges %we study the $proper$ $connection$ $number$ is under the conditions of adding the minimum degree and optimizing the number of edges. our main result is the following, by adding a minimum degree condition: Let $G$ be a connected graph of order $n$, $k\ge 3$. If $|E(G)|\ge \left(\genfrac{}{}{0ex}{}{n-m-(k+1-m)(\delta +1)}{2}\right)+(k+1-m)\left(\genfrac{}{}{0ex}{}{\delta +1}{2}\right)+k+2$, then $pc(G)\le k$, where $m$ takes the value $t$ if $\delta =1$ and $\lfloor \frac{k}{\delta -1}\rfloor$ if $\delta \ge 2$. Furthermore, if $k=2$ and $\delta =2$, %(i.e., $|E(G)|\ge \left(\genfrac{}{}{0ex}{}{n-5}{2}\right)+7$) $pc(G)\le 2$, except $G\in \{G_1,G_n\}$ ($n\ge 8$), where $G_1=K_1\vee 3K_2$ and $G_n$ is obtained by taking a complete graph $K_{n-5}$ and $K_1\vee (2K_2$) with an arbitrary vertex of $K_{n-5}$ and a vertex with $d(v)=4$ in $K_1\vee (2K_2$) being joined. If $k=2$, $\delta \ge 3$, we conjecture $pc(G)\le 2$, where $m$ takes the value $1$ if $\delta =3$ and $0$ if $\delta \ge 4$ in the assumption.

12. arXiv admin note: text overlap with arXiv:1601.04162 and arXiv:1602.07163 by other authors