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'(H) \) colors is a subgraph of some distance-colored graph and the question of determining the smallest order of such a graph is studied.