Distant irregularity strength of graphs with bounded minimum degree

Abstract

Consider a graph $G=(V,E)$ without isolated edges and with maximum degree $\Delta$. Given a colouring $c:E\to \{1,2,\dots ,k\}$, the weighted degree of a vertex $v\in V$ is the sum of its incident colours, i.e., ${\sum }_{e\ni v}c(e)$. For any integer $r\ge 2$, the least $k$ admitting the existence of such $c$ attributing distinct weighted degrees to any two different vertices at distance at most $r$ in $G$ is called the $r$-distant irregularity strength of $G$ and denoted by $s_r(G)$. This graph invariant provides a natural link between the well known 1--2--3 Conjecture and irregularity strength of graphs. In this paper we apply the probabilistic method in order to prove an upper bound $s_r(G)\le (4+o(1)){\Delta }^{r-1}$ for graphs with minimum degree $\delta \ge {\ln }^8\Delta$, improving thus far best upper bound $s_r(G)\le 6{\Delta }^{r-1}$.

11 pages

References in corpus (1)

• Distant total irregularity strength of graphs via random vertex ordering

Cited by in corpus (2)

• Distant sum distinguishing index of graphs
• Distant total irregularity strength of graphs via random vertex ordering