scientific article; zbMATH DE number 1506504
Let \(G\) be a graph with at most one trivial component and no component isomorphic to \(K_2\). Then \(G\) has an irregular labeling, i.e. an assignment of positive integer weights to the edges such that the sums of the edge weights incident to each vertex are distinct. There are two measures of the irregularity of \(G\). The largest weight used by an irregular labeling is called the strength and the irregularity strength of \(G\) is the smallest strength over all irregular labelings of \(G\). A related notion, the irregularity cost, \(\text{ic}(G)\), is the smallest sum of labels for which an irregular labeling of \(G\) exists. (This notion is also known as the irregularity sum; see \textit{M. S. Jacobson, E. Kubicka}, and \textit{G. Kubicki} [Vishwa Internat. J. Graph Theory 1, No. 2, 159-175 (1992)].) In this paper, the author shows that if \(T\) is a tree on \(n\) vertices, then \[ \begin{aligned} \frac{n^2-3n+4}4&\leq \text{ ic}(T)\leq\binom{n-1}2\quad \text{ if } n\equiv 0\;\text{ or } 3\pmod 4 \text{ and }\\\frac{n^2-3n+6}4&\leq \text{ ic}(T)\leq\binom{n-1}2 \quad\text{ if } n\equiv 1 \text{ or } 2\pmod 4.\end{aligned} \] Furthermore, these bounds are shown to be sharp.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4504897)