On Color-Connected Graphs

Abstract

For a connected graph $G$ and a positive integer $k$, the $k$th power $G^k$ of $G$ is the graph with $V(G^k)=V(G)$ where $uv\in E(G^k)$ if the distance $d_G(u,v)$ between $u$ and $v$ is at most $k$. The edge coloring of $G^k$ defined by assigning each edge $uv$ of $G^k$ the color $d_G(u,v)$ produces an edge-colored graph $G^k$ called a distance-colored graph. A distance-colored graph is properly $p$-connected if every two distinct vertices $u$ and $v$ in the graph are connected by $p$ internally disjoint properly colored $u$-$v$ paths. It is shown that $G^2$ is properly $2$-connected for every $2$-connected graph that is not complete, a double star is the only tree $T$ for which $T^2$ is properly $2$-connected, and $G^3$ is properly $2$-connected for every connected graph $G$ of diameter at least $3$. All pairs $k,n$ of positive integers for which $P_n^k$ is properly $k$-connected are determined. It is shown that every properly colored graph $H$ with ${\chi }^{\prime }(H)$ colors is a subgraph of some distance-colored graph and the question of determining the smallest order of such a graph is studied.