zbMATH — the first resource for mathematics

An iterative approach to graph irregularity strength. (English) Zbl 1213.05119
Summary: An assignment of positive integer weights to the edges of a simple graph \(G\) is called irregular if the weighted degrees of the vertices are all different. The irregularity strength, \(s(G)\), is the maximal edge weight, minimized over all irregular assignments, and is set to infinity if no such assignment is possible. In this paper, we take an iterative approach to calculating the irregularity strength of a graph. In particular, we develop a new algorithm that determines the exact value \(s(T)\) for trees \(T\) in which every two vertices of degree not equal to two are at distance at least eight.

05C22 Signed and weighted graphs
Full Text: DOI
[1] Amar, D.; Togni, O., Irregularity strength of trees, Discrete math., 190, 15-38, (1998) · Zbl 0956.05092
[2] Bohman, T.; Kravitz, D., On the irregularity strength of trees, J. graph theory, 45, 241-254, (2004) · Zbl 1034.05015
[3] Cammack, L.; Schelp, R.; Schrag, G., Irregularity strength of full \(d\)-ary trees, Congr. numer., 81, 113-119, (1991) · Zbl 0765.05037
[4] Chartrand, G.; Jacobson, M.S.; Lehel, J.; Oellermann, O.R.; Ruiz, S.; Saba, F., Irregular networks, Congr. numer., 64, 187-192, (1988)
[5] Frieze, A.; Gould, R.; Karonski, M.; Pfender, F., On graph irregularity strength, J. graph theory, 41, 120-137, (2002) · Zbl 1016.05045
[6] Kinch, L.; Lehel, J., The irregularity strength of \(t P_3\), Discrete math., 94, 1, 75-79, (1991) · Zbl 0778.05079
[7] Lehel, J., Facts and quests on degree irregular assignments, (), 765-781 · Zbl 0841.05052
[8] Nierhoff, T., A tight bound on the irregularity strength of graphs, SIAM J. discrete math., 13, 313-323, (2000) · Zbl 0947.05067
[9] Przybyło, J., Irregularity strength of regular graphs, Electron. J. combin., 15, #R82, (2008) · Zbl 1163.05329
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.