Irregularity Strength

Consider a simple graph with no isolated edges and at most one isolated point. Assign each edge a positive integer weight , and define the corresponding vertex labels to be equal to the sum of weights of edges incident on . Then the irregularity strength of a graph (also denoted , e.g., Dinitz et al. 1992), is the smallest value of such that the vertex weights are all distinct (Chartrand et al. 1988, Przybylo 2024).

Define for a graph with one or more isolated edges or more than one isolated point.

For any graph other than the triangle graph on vertices with finite irregularity strength,

(1)

(Nierhoff 2000, Przybylo 2024), with equality for star graphs with (Przybylo 2024).

For a connected graph on vertices, Chartrand et al. (1988) gave the lower bound

(2)

where is the number of vertices of vertex degree and is the maximum vertex degree of . For a regular graph of degree , this condition reduces to

(3)

(Przybylo 2024). Another bound attributed to Jacobson and Lehel defines

(4)

then

(5)

(Ebert et al. 1990, Dinitz et al. 1992, Bohman and Kravitz 2004). Note that some authors (e.g., Ebert et al. 1990, Bohman and Kravtiz 2004) leave as the potentially rational number defined above, while others (e.g., Dinitz et al. 1992) explicitly add a ceiling function around the right hand side to make it an integer.

For a graph with minimum vertex degree ,

(6)

(Kalkowski et al. 2011, Przybylo 2024).

Faudree and Lehel (1987) conjectured that there exists an absolute constant such that for every -regular graph with vertices and ,

(7)

(Przybylo 2024).