Distant sum distinguishing index of graphs with bounded minimum degree
Abstract
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∋uc(e) ≠ ∑e∋vc(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 Δ.
Keywords
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