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 $$\chi ^{\prime }_{\mathrm{d2}}(G)$$ χ d 2 ′ ( G ) 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 $$\chi ^{\prime }_{\mathrm{d2}}(G)\le 6$$ χ d 2 ′ ( G ) ≤ 6 . Since the Peterson graph P satisfies $$\chi ^{\prime }_{\mathrm{d2}}(P)=5$$ χ d 2 ′ ( P ) = 5 , our solution is within one color from optimal.