zbMATH — the first resource for mathematics

On the irregularity strength of the \(m\times n\) grid. (English) Zbl 0771.05055
The irregularity strength of a graph \(G\) is the minimum positive integer \(I(G)\) such that positive integer weights \(\leq I\) can be assigned to the edges of \(G\) such that each vertex has a different weighted degree. The irregularity strength of the \(m\times n\) grid is determined for many \(m\) and \(n\). In particular, for any positive integer \(d\), the irregularity strength for all but a finite number of \(m\times n\) grids with \(n-m=d\) is determined. Intricate and interesting lower bound examples are described.

05C35 Extremal problems in graph theory
05C99 Graph theory
Full Text: DOI
[1] Chartrand, Congres. Numer. 64 pp 197– (1988)
[2] , and , Irregularity strength of full d-ary trees. Preprint. · Zbl 0765.05037
[3] and , Minimal irregular weightings of Xm, n for 3 m, n 16. Research Report 91-8, Department of Mathematics and Statistics, University Vermont, Burlington, June (1991).
[4] Ebert, Congres. Numer. 71 pp 39– (1990)
[5] Faudree, Discrete Math. 91 pp 45– (1991)
[6] Faudree, Discrete Math. 76 pp 223– (1989)
[7] Garnick, J. Combinat. Math. Combinat. Comput. 8 pp 195– (1990)
[8] Gyárfás, Discrete Math 71 pp 273– (1988)
[9] Gyárfás, Utilitas Math. 35 pp 111– (1989)
[10] and , A bound for the strength of an irregular network. Preprint.
[11] Kinch, Ars Combinat.
[12] Facts and quests on degree irregular assignments. Graph Theory, Combinatorics, and Applications. John Wiley & Sons, New York (1991) 765–782. · Zbl 0841.05052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.