Distant sum distinguishing index of graphs with bounded minimum degree

Jakub Przybyło

Ars Mathematica Contemporanea, Tome 17 (2019) no. 1, pp. 37-49.

Résumé

For any graph G = (V, E) with maximum degree Δ and without isolated edges, and a positive integer r, by χ′Σ, r(G) we denote the r-distant sum distinguishing index of G. This is the least integer k for which a proper edge colouring c: E → {1, 2, …, k} exists such that ∑e∋u c(e) ≠ ∑e∋v c(e) for every pair of distinct vertices u, v at distance at most r in G. It was conjectured that χ′Σ, r(G) ≤ (1 + o(1))Δr − 1 for every r ≥ 3. Thus far it has been in particular proved that χ′Σ, r(G) ≤ 6Δr − 1 if r ≥ 4. Combining probabilistic and constructive approach, we show that this can be improved to χ′Σ, r(G) ≤ (4 + o(1))Δr − 1 if the minimum degree of G equals at least ln8 Δ.

Détail

DOI : 10.26493/1855-3974.1496.623

Keywords: Distant sum distinguishing index of a graph, neighbour sum distinguishing index, adjacent strong chromatic index, distant set distinguishing index