Consider a simple graph with no isolated edges and at most one isolated point. Assign 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,
![s(G)<=n-1](/images/equations/IrregularityStrength/NumberedEquation1.svg) |
(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
![s(G)<=max_(1<=i<=Delta)(n_i+i-1)/i,](/images/equations/IrregularityStrength/NumberedEquation2.svg) |
(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
![s(G)>=(n+d-1)/d](/images/equations/IrregularityStrength/NumberedEquation3.svg) |
(3)
|
(Przybylo 2024). Another bound attributed to Jacobson and Lehel defines
![lambda(G)=max_(1<=i<=j)((sum_(k=i)^(j)n_k)+i-1)/j,](/images/equations/IrregularityStrength/NumberedEquation4.svg) |
(4)
|
then
![s(G)>=lambda(G),](/images/equations/IrregularityStrength/NumberedEquation5.svg) |
(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
,
![s(G)<=6[n/delta]](/images/equations/IrregularityStrength/NumberedEquation6.svg) |
(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
,
![s(G)<=n/d+C](/images/equations/IrregularityStrength/NumberedEquation7.svg) |
(7)
|
(Przybylo 2024).
See also
Irregular Graph,
Regular
Graph
Explore with Wolfram|Alpha
References
Amar, D. "Irregularity Strength of Regular Graphs of Large Degree." Disc. Math. 114, 9-17, 1993.Anholcer,
M. and Palmer, C. "Irregular Labellings of Circulant Graphs." Discr.
Math. 312, 3461-3466, 2012.Bača, M.; Imran, M.; and
Semaničová-Feňovčková', A. "Irregularity
and Modular Irregularity Strength of Wheels." Mathematics 9, 2710,
2021.Bohman, T. and Kravitz, D. "On the Irregularity Strength of
Trees." J. Graph Th. 45, 241-254, 2004.Chartrand,
G.; Jacobson, M. S.; Lehel, J.; Oellermann, O. R.; Ruiz, S.; and Saba,
F. "Irregular Networks." Congr. Numer. 64, 197-210, 1988.Dinitz,
J. H.; Garnick, D. K.; and Gyárfás, A. "On the Irregularity
Strength of the
Grid." J. Graph Th. 16, 355-374, 1992.Ebert, G.,
Hemmeter, J.; Lazebnik F.; and Woldar, A. "On the Number of Irregular Assignments
on a Graph." Disc. Math. 93, 141-142, 1991.Ebert,
G.; Hammenter, J.; Lazebnik, F.; and Woldar, A. "Irregularity Strengths for
Certain Graphs." Congr. Numer. 71, 39-52, 1990.Faudree,
R.; Schelp, R.; Jacobson, M.; and Lehel, J. "Irregular Networks, Regular Graphs
and Integer Matrices With Distinct Row and Column Sums." Disc. Math. 76,
223-240, 1989.Faudree, R. J. and Lehel, J. "Bound on the Irregularity
Strength of Regular Graphs." In Colloq. Math. Soc. Janós Bolyai, Vol. 52,
Combinatorics, Eger. Amsterdam, Netherlands: North-Holland, pp. 247-256,
1987.Gallian, J. §7.13 in "Dynamic Survey of Graph Labeling."
Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gyarfas,
A. "The Irregularity Strength of
is 4 for
Odd." Discr. Math. 71, 273-274, 1988.Jacobson,
M. S. and Lehel, J. "A Bound for the Strength of an Irregular Network."
Preprint.Jendroľ, S. and Tkác, M. "The Irregularity
Strength of
."
Disc. Math. 145, 301-305, 1995.Jendrol', S. and oldák,
V. "The Irregularity Strength of Generalized Petersen Graphs." Math.
Slovaca 45, 107-113, 1995.Jinnah, M. I. and Santhosh
Kumar, K. R. "Irregularity Strength of Triangular Snake and Double Triangular
Snake." Adv. Appl. Disc. Math. 9, 83-92, 2012.Kalkowski,
M.; Karoński, M.; and Pfender, F. "A New Upper Bound for the Irregularity
Strength of Graphs." SIAM J. Disc. Math. 25, 1319-1321, 2011.Lehel,
J. "Facts and Quests on Degree Irregular Assignments." In Graph
Theory, Combinatorics and Applications: Proceedings of the Sixth Quadrennial International
Conference on the Theory and Applications of Graphs, Western Michigan University
(Ed. Y. Alavi, F. R. K. Chung, R. L. Graham, and D. F. Hsu).
New York: Wiley, pp 765-782 1991.Nierhoff, T. "A Tight Bound
on the Irregularity Strength of Graphs." SIAM J. Disc. Math. 13,
313-323, 2000.Przybylo, J. "The Irregularity Strength of Dense
Graphs--On Asymptotically Optimal Solutions of Problems of Faudree, Jacobson, Kinch
and Lehel." 13 Jun 2024. https://arxiv.org/abs/2406.09584.
Cite this as:
Weisstein, Eric W. "Irregularity Strength."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IrregularityStrength.html