2016/10/16 by Robert Melville, Melville, Robert, Wayne Goddard +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1610.04874
For a connected graph, we define the proper-walk connection number as the minimum number of colors needed to color the edges of a graph so that there is a walk between every pair of vertices without two consecutive edges having the same color. We show that the proper-walk connection number is at most three for all cyclic graphs, and at most two for bridgeless graphs. We also characterize the bipartite graphs that have proper-walk connection number equal to two, and show that this characterization also holds for the analogous problem where one is restricted to properly colored paths.