Two-distance vertex-distinguishing index of sparse graphs

Abstract

The two-distance vertex-distinguishing index χd2′(G){\chi }_{d2}^{^{\prime} }\left(G) of graph GG is defined as the smallest integer kk, for which the edges of GG can be properly colored using kk colors. In this way, any pair of vertices at distance of two have distinct sets of colors. The two-distance vertex-distinguishing edge coloring of graphs can be used to solve some network problems. In this article, we used the method of discharging to prove that if GG is a graph with mad(G)<83\left(G)\lt \frac{8}{3}, then χd2′(G)≤max{7,Δ+2}{\chi }_{d2}^{^{\prime} }\left(G)\le \max \left\{7,\Delta +2\right\}, which improves the result that a graph GG of Δ(G)≥4\Delta \left(G)\ge 4 has χd2′(G)≤Δ(G)+2{\chi }_{d2}^{^{\prime} }\left(G)\le \Delta \left(G)+2 if mad(G)<52\left(G)\lt \frac{5}{2}, and χd2′(G)≤Δ(G)+3{\chi }_{d2}^{^{\prime} }\left(G)\le \Delta \left(G)+3 if mad(G)<83\left(G)\lt \frac{8}{3}.

Keywords

• two-distance vertex-distinguishing index
• edge coloring
• maximum average degree
• 05c15