Contents

-

On Color-Connected Graphs

Ryan Jones1, Kyle Kolasinski1, Chira Lumduanhom1, Ping Zhang1
1Department of Mathematics, Western Michigan University Kalamazoo, MI 49008-5248 USA

Abstract

For a connected graph G and a positive integer k, the kth power Gk of G is the graph with V(Gk)=V(G) where uvE(Gk) if the distance dG(u,v) between u and v is at most k. The edge coloring of Gk defined by assigning each edge uv of Gk the color dG(u,v) produces an edge-colored graph Gk 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 G2 is properly 2-connected for every 2-connected graph that is not complete, a double star is the only tree T for which T2 is properly 2-connected, and G3 is properly 2-connected for every connected graph G of diameter at least 3. All pairs k,n of positive integers for which Pnk is properly k-connected are determined. It is shown that every properly colored graph H with χ(H) colors is a subgraph of some distance-colored graph and the question of determining the smallest order of such a graph is studied.