Distant sum distinguishing index of graphs with bounded minimum degree

Jakub Przybyło


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 ∑euc(e) ≠ ∑evc(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 Δ.


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

Full Text:


DOI: https://doi.org/10.26493/1855-3974.1496.623

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications