Distance proper connection of graphs and their complements

Abstract

Let $G$ be an edge-colored connected graph. A path $P$ in $G$ is called a distance $\ell$-proper path if no two edges of the same color can appear with less than $\ell$ edges in between on $P$. The graph $G$ is called $(k,\ell )$-proper connected if there is an edge-coloring such that every pair of distinct vertices of $G$ are connected by $k$ pairwise internally vertex-disjoint distance $\ell$-proper paths in $G$. The minimum number of colors needed to make $G$ $(k,\ell )$-proper connected is called the $(k,\ell )$-proper connection number of $G$ and denoted by $p{c}_{k,\ell }(G)$. In this paper we first focus on the $(1,2)$-proper connection number of $G$ depending on some constraints of $\overline{G}$. Then, we characterize the graphs of order $n$ with $(1,2)$-proper connection number $n-1$ or $n-2$. Using this result, we investigate the Nordhaus-Gaddum-Type problem of $(1,2)$-proper connection number and prove that $p{c}_{1,2}(G)+p{c}_{1,2}(\overline{G})\le n+2$ for connected graphs $G$ and $\overline{G}$. The equality holds if and only if $G$ or $\overline{G}$ is isomorphic to a double star.

16 pages. arXiv admin note: text overlap with arXiv:1606.06547