2-Distance vertex-distinguishing index of subcubic graphs

A 2-distance vertex-distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices at distance 2 have distinct sets of colors. The 2-distance vertex-distinguishing index of G is the minimum number of colors needed for a 2-distance vertex-distinguishing edge coloring of G. Some network problems can be converted to the 2-distance vertex-distinguishing edge coloring of graphs. It is proved in this paper that if G is a subcubic graph, then . Since the Peterson graph P satisfies , our solution is within one color from optimal.