Distant total irregularity strength of graphs via random vertex ordering

Abstract

Let $c:V\cup E\to \{1,2,\dots ,k\}$ be a (not necessarily proper) total colouring of a graph $G=(V,E)$ with maximum degree $\Delta$. Two vertices $u,v\in V$ are sum distinguished if they differ with respect to sums of their incident colours, i.e. $c(u)+{\sum }_{e\ni u}c(e)\ne c(v)+{\sum }_{e\ni v}c(e)$. The least integer $k$ admitting such colouring $c$ under which every $u,v\in V$ at distance $1\le d(u,v)\le r$ in $G$ are sum distinguished is denoted by ${\mathrm{ts}}_r(G)$. Such graph invariants link the concept of the total vertex irregularity strength of graphs with so called 1-2-Conjecture, whose concern is the case of $r=1$. Within this paper we combine probabilistic approach with purely combinatorial one in order to prove that ${\mathrm{ts}}_r(G)\le (2+o(1)){\Delta }^{r-1}$ for every integer $r\ge 2$ and each graph $G$, thus improving the previously best result: ${\mathrm{ts}}_r(G)\le 3{\Delta }^{r-1}$.

8 pages

References in corpus (2)

• Distant irregularity strength of graphs with bounded minimum degree
• Total Vertex Irregularity Strength of Forests

Cited by in corpus (2)

• Distant irregularity strength of graphs with bounded minimum degree
• Distant total sum distinguishing index of graphs